数据结构自学考试试卷

一 单项选择题(本大题共 小题 每小题 分 共 分)

在每小题列出的四个备选项中只有一个是符合题目要求的 请将其代码填写在题后的括号内 错选 多选或未选均无分

在数据结构中 数据的逻辑结构可以分成()

A 内部结构和外部结构 B 线性结构和非线性结构

C 紧凑结构和非紧揍结构 D 动态结构和静态结构

在以单链表为存储结构的线性表中 数据元素之间的逻辑关系用()

A 数据元素的相邻地址表示 B 数据元素在表中的序号表示

C 指向后继元素的指针表示 D 数据元素的值表示

设 p 指向单链表中的一个结点 s 指向待插入的结点 则下述程序段的功能是()

s > next = p > next; p > next = s;

t = p > data; p > data = s > data; s >data = t;

A 结点 *p 与结点 *s 的数据域互换

B 在 p 所指结点的元素之前插入元素

C 在 p 所指结点的元素之后插入元素

D 在结点 *p 之前插入结点 *s

栈和队列都是()

A 限制存取位置的线性结构 B 顺序存储的线性结构

C 链式存储的线性结构 D 限制存取位置的非线性结构

若数组 s[ n ] 为两个栈 s 和 s 的共用存储空间 且仅当 s[ n ] 全满时 各栈才不能进行进栈操作 则为这两个栈分配空间的最佳方案是 s 和 s 的栈顶指针的初值分别为()

A 和 n+ B 和 n/

C 和 n D 和 n+

执行下列程序段后 串 X 的值为()

S= 〞 abcdefgh 〞 ; T= 〞 xyzw 〞 ;

substr (X S strlen(T));

substr (Y S stelen(T) );

strcat (X Y);

A 〞 cdefgh 〞 B 〞 cdxyzw 〞

C 〞 cdefxy 〞 D 〞 cdefef 〞

多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为()

A 数组的元素处在行和列两个关系中 B 数组的元素必须从左到右顺序排列

C 数组的元素之间存在次序关系 D 数组是多维结构 内存是一维结构

从广义表 LS =( (p q) r s )中分解出原子 q 的运算是()

A tail (head (LS)) B head (tail (head (LS)))

C head (tail (LS)) D tail (tail (head (LS)))

在具有 n 个叶子结点的严格二叉树中 结点总数为()

A n+ B n

C n D n

若 是有向图的一条边 则称()

A v i 邻接于 v j B v j 邻接于 v i

C v i 和 v j 相互邻接 D v i 与 v j 不相邻接

在一个带权连通图 G 中 权值最小的边一定包含在 G 的()

A 最小生成树中 B 深度优先生成树中

C 广度优先生成树中 D 深度优先生成森林中

当在二叉排序树中插入一个新结点时 若树中不存在与待插入结点的关键字相同的结点 且新结点的关键字小于根结点的关键字 则新结点将成为()

A 左子树的叶子结点 B 左子树的分支结点

C 右子树的叶子结点 D 右子树的分支结点

希尔排序的增量序列必须是()

A 递增的 B 随机的

C 递减的 D 非递减的

如果在排序过程中 每次均将一个待排序的记录按关键字大小加入到前面已经有序的子表中的适当位置 则该排序方法称为()

A 插入排序 B 归并排序

C 冒泡排序 D 堆排序

设置溢出区的文件是()

A 索引非顺序文件 B ISAM 文件

C VSAM 文件 D 顺序文件

二 填空题(本大题共 小题 每小题 分 共 分)

请在每小题的空格中填上正确答案 错填 不填均无分

下列程序段的时间复杂度为 ________________

product = ;

for (i = n;i> ; i )

for (j = i+ ; j

product *=j;

17 .已知指针 p 指向单链表中某个结点，则语句 p -> next =p -> next -> next 的作用是 ________________ 。WiNGwit.

18 .假设元素只能按 a,b,c,d 的顺序依次进栈，且得到的出栈序列中的第一个元素为 c ，则可能得到的出栈序列为 ________________ ，不可能得到的出栈序列为 ________________ 。

19 .若链串结点中的指针占 4 个字节，每个字符占 1 个字节，则结点大小为 2 的链串的存储密度为 ________________ 。

20 .右图表示的广义表为 ________________ 。

21 .若一棵满三叉树中含有 121 个结点，则该

树的深度为 ________________ 。

22 .若以邻接矩阵表示有向图，则邻接矩阵上

第 i 行中非零元素的个数即为顶点 v i 的 ________________ 。

23 .若希望只进行 8 趟排序便能在 4800 个元素中找出其中值最小的 8 个元素，并且要求排序过程中所进行的关键字比较次数尽可能少，则应该选用 ________________ 排序方法。

24 .在含 20 个关键字的 3 阶 B 树( 2 - 3 树)上查找一个关键字，至多需要访问 ___________ 次外存。

25 .文件上的两类主要操作为 ________________ 和 ________________ 。

三、解答题(本大题共 4 小题，每小题 5 分，共 20 分)

26 .设栈 S1 的入栈序列为 1 2 3 4 (每个数字为 13 个元素)，则不可能得到出栈序列 3142 。但可通过增设栈 S2 来实现。例如，按下图中的箭头指示，依次经过栈 S1 和 S2 ，便可得到序列 3 1 4 2 。

如果用 H1 和 H2 分别表示栈 S1 和 S2 的进栈操作，用 P1 和 P2 分别表示两个栈的出栈操作，则得到 3 1 4 2 的一个操作步骤为

H1 ， H1 ， H1 ， P1 ， H2 ， P2 ， P1 ， H2 ， P1 ， H2 ， P2 ， H1 ， P1 ， H2 ， P2 ， P2

请仿照上例写出利用两个栈从 1 2 3 4 得到 4 1 3 2 的操作步骤。

27 .已知树如右图所示，

( 1 )写出该树的后序序列;

( 2 )画出由该树转换得到的二叉树。

28 .为关键字( 17 ， 33 ， 31 ， 40 ， 48 )构造一个长度为 7 的散列表，设散列函数为 h(key)=key%7, 用开放定址法解决冲突的探查序列是

hi = (h(key) + i(key%5+1))%7 0 ≤ i ≤ 6

( 1 )画出构造所得的散列表;

( 2 )求出在等概率情况下查找成功时的平均查找长度。

29 .已知 R [ 1..8 ]中的元素依次为( 12 ， 5 ， 9 ， 20 ， 6 ， 31 ， 24 ， 27 )，写出按算法 MergeSortDC 对 R 进行自顶向下的二路归并排序过程中，前 5 次调用函数 Merge(R, low, mid, high) 时参数 low, mid 和 high 的值。

void MergeSortDC (int R[], int low, int mid, int high )

{

int mid;

if (low

{

mid = (low +high)/2;

MergeSortDC (R, low, mid);

MergeSortDC (R, mid+1, high);

Merge (R, low, mid, high);

}

} // MergeSortDC

( 1 )第一次调用时的参数值;

( 2 )第二次调用时的参数值;

( 3 )第三次调用时的参数值;

( 4 )第四次调用时的参数值;

( 5 )第五次调用时的参数值;

四、算法阅读题(本大题共 4 小题，每小题 5 分，共 20 分)

30 .下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表(表中不存在值相同的数据元素)进行如下操作：将所有在 Lb 表中存在而 La 表中不存在的结点插入到 La 中，其中 La 和 Lb 分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。

void union (LinkList La, LinkList Lb)

{

// 本算法的功能是将所有 Lb 表中存在而 La 表中不存在的结点插入到 La 表中

LinkList pre = La, q;

LinkList pa = La -> next;

LinkList pb = Lb -> next;

free (Lb);

while (pa && pd)

{

if (pa -> data data)

{ pre = pa; pa = pa -> next;}

else if (pa -> data > pb ->data)

{

(1) ;

pre = pb;

pb = pb -> next;

(2) ;

}

else

{

q = pb; pb = pb -> next; free (q);

}

}

if (pb)

(3) ;

}

(1)

(2)

(3)

全国2008年10月高等教育自学考试数据结构试题课程代码：02331一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是最符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ ）A. 栈 B. 队列C. 树 D. 图2.下面程序段的时间复杂度为（ ）for (i=0; inext==head B. p->next->next==headC. p->next==NULL D. p==head4.若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（ ）A. SXSSXXXX B. SXXSXSSXC. SXSXXSSX D. SSSXXSXX5.两个字符串相等的条件是（ ）A. 串的长度相等 B. 含有相同的字符集C. 都是非空串 D. 串的长度相等且对应的字符相同6.如果将矩阵An×n的每一列看成一个子表，整个矩阵看成是一个广义表L，即L=((a11,a21,…,an1),( a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素，则求得a21的运算是（ ）A. head (tail (head (L))) B. head (head(head(L)))C. tail (head (tail (L))) D. head (head (tail (L)))7.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（ ）A. 0 B. 1C. 48 D. 498.在一个具有n个顶点的有向图中，所有顶点的出度之和为Dout ，则所有顶点的入度之和为（ ）A. Dout B. Dout-1C. Dout+1 D. n9.如图所示的有向无环图可以得到的拓扑序列的个数是（ ）A. 3 B. 4C. 5 D. 610.如图所示的带权无向图的最小生成树的权为（ ）A. 51 B. 52C. 54 D. 5611.对长度为n的关键字序列进行堆排序的空间复杂度为（ ）A. O（log2n） B. O（1）C. O（n） D. O（n*log2n）12.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为（35，51，24，13，68，56，42，77，93）（35，24，13，51，56，42，68，77，93）所采用的排序方法是（ ）A. 插入排序 B. 冒泡排序C. 快速排序 D. 归并排序13.已知散列表的存储空间为T[0..18]，散列函数H（key）=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是（ ）A. T[2] B. T[4]C. T[8] D. T[10]14.适宜进行批量处理的文件类型是（ ）A. 顺序文件 B. 索引顺序文件C. 散列文件 D. 多关键字文件15.VSAM文件的索引结构为（ ）A. B+树 B. 二叉排序树C. B-树 D. 最优二叉树二、填空题(本大题共10小题，每小题2分，共20分)请在每小题的空格中填上正确答案。错填、不填均无分。16.如果某算法对于规模为n的问题的时间耗费为T（n）=3n3，在一台计算机上运行时间为t秒，则在另一台运行速度是其64倍的机器上，用同样的时间能解决的问题规模是原问题规模的 倍。17.将两个长度分别为m和n的递增有序单链表，归并成一个按元素递减有序的单链表，可能达到的最好的时间复杂度是 。18.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则在队列不满的情况下，队列的长度是 。19.字符串“sgabacbadfgbacst” 中存在有 个与字符串“ba”相同的子串。20.假设以列优先顺序存储二维数组A[5][8]，其中元素A[0][0]的存储地址为LOC（a00）,且每个元素占4个存储单元，则数组元素A[i][j]的存储地址为 。21.假设用表示树的边（其中x是y的双亲），已知一棵树的边集为{,,,,,}，该树的度是 。22.n个顶点且含有环路的无向连通图中，至少含有 条边。23.在一般情况下用直接插入排序、选择排序和冒泡排序的过程中，所需记录交换次数最少的是 。24.和二分查找相比，顺序查找的优点是除了不要求表中数据元素有序之外，对 结构也无特殊要求。25.顺序文件中记录存放的物理顺序和 顺序一致。三、解答题(本大题共4小题，每小题5分，共20分)26.由森林转换得到的对应二叉树如图所示，写出原森林中第三棵树的前序序列和后序序列。前序序列：后序序列：27.图的邻接表的类型定义如下所示：#define MaxVertexNum 50typedef struct node {int adjvex;struct node *next;}EdgeNode;typedef struct {VertexType vertex;EdgeNode *firstedge;}VertexNode;typedef VertexNode AdjList[MaxVertexNum];typedef struct {AdjList adjlist;int n, e;}ALGraph;为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。题27图28.某类物品的编号由一个大写英文字母及2位数字（0..9）组成，形如E32。运用基数排序对下列物品编号序列进行按字典序的排序，写出每一趟（分配和收集）后的结果。E13，A37，F43，B32，B47，E12，F37，B12第一趟：第二趟：第三趟：29.（1）画出对表长为13的有序顺序表进行二分查找的判定树；（2）已知关键字序列为（12，14，16，21，24，28，35，43，52，67，71，84，99），写出在该序列中二分查找37时所需进行的比较次数。（1）（2）四、算法阅读题（本大题共4小题，每小题5分，共20分）30.已知线性表的存储结构为顺序表，阅读下列算法，并回答问题：（1）设线性表L=（21，-7，-8，19，0，-11，34，30，-10），写出执行f30(&L)后的L状态；（2）简述算法f30的功能。void f30 (SeqList *L) {int i,j;for (i=j=0;ilength; i++)if(L->data[i]>=0){if(i!=j)L->data[j]=L->data[i];j++；}L->length=j;}(1)(2)31.阅读下列算法，并回答问题：（1）Q、Q1和Q2都是队列结构，设队列Q=（1，0，-5，2，-4，-6，9），其中1为队头元素，写出执行f31 (&Q,&Q1,&Q2)之后队列Q、Q1和Q2的状态；（2）简述算法f31的功能。（注：lnitQueue、EnQueue、DeQueue和QueueEmpty分别是队列初始化、入列、出队和判队空的操作）void f31 (Queue*Q, Queue*Q1, Queue*Q2) {int e;lnitQueue (Q1);lnitQueue (Q2);while (!QueueEmpty (Q)) {e=DeQueue (Q);if (e>=0) EnQueue (Q1,e);else EnQueue (Q2,e)}}（1）（2）32.阅读下列算法，并回答问题：（1）假设串由合法的英文字母和空格组成，并以’\0’作结束符。设串s=”⊔⊔|⊔am⊔a⊔⊔⊔student”(⊔表示空格符)，写出f32（s）的返回值；（2）简述算法f32的功能。int f32 (char*s){int i, n, inword;n=inword=0;for (i=0;s[i]!=’\0’;i++)if (s[i]!=’⊔’&& inword==0){inword=1;n++;}else if (s[i]==’⊔’&& inword==1)inword=0;return n;}（1）（2）33.阅读下列对正整数关键字序列L操作的算法，并回答问题：（1）设L=(28,19,27,49,56,12,10,25,20,50),写出f33 (L,4)的返回值；（2）简述函数f33的功能。int Partition (SeqList*L, int low, int high);‖对L[low..high]做划分，返回基准记录的位置，并使左部的关键字‖都小于或等于基准记录的关键字，右部的关键字都大于基准记录的关键字int f33 (SeqList L, int k){int low, high, pivotpos;low=1;high=L.length;if (khigh)return-1;do {pivotpos=Partition (&L, low, high);‖调用快速排序的划分算法if (pivotposk)high=pivotpos-1;}while (pivotpos!=k);return L.data [pivotpos];}（1）（2） 五、算法设计题（本题10分）34.二叉排序树的类型定义如下：typedef struct BSTNode {‖ 二叉排序树的结点结构int data; ‖数据域struct BSTNode *lchild, *rchild; ‖左、右孩子指针}BSTNode,*BSTree;设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。