数据结构模拟试题二及答案

数据结构模拟试题二

一．判断题（每小题1 分，共15分） 1. 构成数据的最小单位是数据项。

2. 空线性表的一个特性是线性表中各结点尚未赋值。 3. 非循环单向链表一定要有表头指针。

4. 顺序栈的栈顶指针是一个指针类型的变量。

5. 在表示树的双亲数组中，找结点的双亲要比找结点的孩子容易。 6. 哈夫曼树中不存在度为1的结点。

7. 在图中，与Vi相邻的顶点其序号一定是i+1或i-1。

8. 如果是不连通的无向图，则在相应的邻接表中一定有空链表。 9. 矩阵的行数和列数可以不相等。

10. 广义表的深度与广义表中含有多少个子表元素有关。 11. 折半查找可以在有序的双向链表上进行。

12. 散列查找过程中，关键字的比较次数和散列表中关键字的个数直接相关。 13. 对n个元素执行简单选择排序，排序码的比较次数总是n(n-1)/2次。 14. 物理记录的大小与逻辑记录的大小成正比。

15. 对索引文件，索引表是建立在内存的，数据区是建立在外存的。 二．填空题（每空1分，共15分）

1. 在程序中，描述顺序表的存储空间一般用________变量。

2. 若用Q[0]~Q[100]作为循环顺序队列的存储空间，用“队首指针f的值等于队尾指针r

的值”作为队空的标志，则创建一个空队列所要执行的操作是___________。 3. 栈和顺序栈的区别仅在于________。

4. n个结点的二叉树最大高度是___，最小高度是___。 5. 树的存储方法主要有_____、_____和_____三种。 6. n个顶点的强连通图中至少有___条边。 7. 10行20列矩阵若用列优先顺序表来表示，则矩阵中第7行第6列元素是顺序表中第___

个元素。

8. 在各元素查找概率相等的情况下，在含有14个元素的平衡二叉排序树上查找其中一个

元素，元素间的平均比较次数至少是_____次，至多是______次。

9. 对n个元素执行快速排序，在进行第一次分组时，元素的移动次数至多是____次，至少

是___次。

10. 在B-树中，若某结点有i个孩子，则该结点中一定有___个关键字。 三．选择题（每题2分，共30分）

1.数据结构的研究内容不涉及________。

A．算法用什么语言来描述 B．数据如何存储 C．数据的运算如何实现 D．数据如何组织

2. 若H1是动态单向链表的表头指针，H2是动态双向链表的表头指针，则________。 A．H1和H2占用同样多的内存空间 B．H1和H2是同类型的变量 C．H2要比H1占用更多的内存空间

D．双向链表要比单向链表占用更多的内存空间

3. 对于K个带头结点的静态单向链表来说，若各结点类型相同，则K个链表一般可共用_________。

A．同一个数组 B．某些数组元素 C．同一个表头结点 D同一个表头指针 4.最不适合用作链接栈的链表是_____________。 A．只有表头指针没有表尾指针的循环双向链表 B．只有表尾指针没有表头指针的循环双向链表 C．只有表尾指针没有表头指针的循环单向链表 D．只有表头指针没有表尾指针的循环单向链表 5.栈和队列的共同点在于_____________。

A．都对存储方法作了限制 B．都是只能进行插入、删除运算 C．都对插入、删除的位

置作了限制 D．都对插入、删除两种操作的先后顺序作了限制

6.如果5个元素的出栈的顺序是1,2,3,4,5，则进栈的顺序可能是_____________。 A．3,5,4,1,2 B.1,4,5,3,2 C.2,4,3,1,5 D.5,1,3,2,4

7.若某棵二叉树结点的后序序列和层次序列正好相反，则该二叉树_____________。

A．每个结点都没有右孩子 B．不存在度为2的结点 C．每个结点都没有左孩子 D．不存在

8.对于一棵具有n个结点，度为3的树来说，树的高度至少是____________。 A．┏log32n┓ B．┏log3(3n-1)┓ C．┏log3(3n+1)┓ D．┏log3(2n+1)┓ 9．对n个顶点的带权连通图来说，它的最小生成树是指图中任意一个由n-1条__________。 A．权值最小的边构成的子图 B．权值之和最小的边构成的子图 C．权值之和最小的边构成的连通子图 D．权值之和最小的边构成的无环子图 10. 所谓特殊矩阵是指_____________比较特殊。 A．矩阵元素之间的关系 B．矩阵的处理方法 C．矩阵元素的取值 D．矩阵的存储方法

11.若长度为n且有n种不同原子的广义表用链接方法存储，则时间复杂度为O（n）的运算是___________。

A．复制一个广义表 B．求广义表的长度 C．查找某个子表 D．查找某个原子

12. 待查找元素关键字的值依次是47，且已存入变量k中，如果在查找过程中，和K进行比较的关键字值依次是47,32,46,25,47,则采用的查找方法____。

A．是一种错误的查找方法 B．可能是分块查找 C．可能是顺序查找 D．可能是折半查找

13．如果元素R1和R2有相同的排序码，并且进行堆排序前，R1在R2的前面，则当排序结束后，___________。

A．R1一定在R2的前面 B．R1一定在R2的后面

C．R1有可能在R2的后面 D．选择R1或R2中的一个留在线性表中

14.下面4种排序方法中，属于稳定的排序方法是_________排序和_________排序。 A．堆 B．基数 C. 快速 D. 起泡

15．在线性表中元素很多，且各元素已有序排列的情况下，执行_______排序或_________排序，排序码比较次数最多。

A．简单选择 B．堆 C．归并 D．堆 四．图表题（每小题4分，共8分）

1.已知5个叶子结点的权值分别为2，5，5，6，9，13 请画出相应的哈夫曼树。 2.对图1所示无向网络，画出从顶点V6开始用普里姆方法构造的最小生成树。 五．算法填空题（每空2分，共8分）

假设待排序的n个元素已存放在顺序表R[1]~R[n]中，排序码字段名是key。下面的算法用于对顺序表进行归并排序，请在空内填入适当内容，将算法补充完整。 Void mergesort(list R, list S, int i, int j){

2 3 Inta,b,c,k;

If (I

(1)____________________________ 2 While ((a<=k)&&(b<=j)) 3 4 3 { If (R[a].key<=R[b].key)

3 2 { S[c]=R[a];

图1 a++;

} Else {

(2)____________________________ }

c++; }

(3)____________________________ While (b<=j) {

S[c]=R[b]; b++; c++; }

(4)____________________________ } }

六．算法设计题（每小题12分，共24分）

1.假设head是某个带头结点单链表的表头指针，每个结点数值字段的类型为整型。写一个算法，从该链表中删除一个值最大的结点，并将该结点的值存入表头结点的数值字段。 2.如果一个十进制正整数首位数字不为零，而且从左往右读和从右往读都一样，则称其为回文数。对一个n位的正整数x，反复执行下列操作，有可能得到一个回文数： （1）生成一个位数和x相同的正整数y，其中yi=xn-i+1,i=1,2,3?; （2）将y累加到x中。

如对于正整数87，按上述方法重复4次后，将得到回文数4884： 87+78=165 165+561=726 726+627=1353 1353+3531=4884

写一个按上述方法求回文数的算法。要求：x的初始值从键盘输入，其位数最多允许10位。如果得到回文数，就输出这个数，并输出上述步骤重复执行的次数，如果上述步骤重复了30次还得不到回文数，则放弃。

数据结构模拟题二参考答案

一.判断题

1、× 2、× 3、√ 4、× 5、√ 6、√ 7、×. 8、× 9、√ 10、× 11、×12、× 13、√ 14、×. 15、× 二．填空题

1.数组 2.给f和r赋同一个值x,0≤x≤100 3.前者没有指定存储方法,后者指定存储方法 4.n ┏log2(n+1)┐ 5.双亲数组 孩子链表 左孩子和右兄弟链表 6.n 7. 57

45478.1414 9.n+1 2 10.i-1 三.选择题

1.A 2.A 3.A 4.D 5.C 6.D 7.B 8.D 9.D 10.C 11.B 12.B 13.C 14.BD 15.AB

四.图表题 1.

40 16 24 7 9 11 13 2 5 5 6

2.有两种可能,如下图所示

2 2 1 2 3 1 2 5 2 2 4 5 6 4 3 2 7 8 9 7 3 2 3 五.(1) a=i; b=k+1; c=i; (2)S[c]=R[b]; b++; (3)while (4)for(k=i; k<=j; k++) R[k]=S[k]; 六.算法设计题 1.Struct node{ int data; node* next; }

typedef node* pointer; pointer head; voiddel(){

pointerp,q,r,s;

q=head; p=q->next; s=q; r=p;

while (r!=Null){

if (r->data>p->data){ q=s; p=r; }

s=r; r=r->next; }

q->next=p->next; p->next=head; head=p; }

2.constmaxlength=40,maxtimes=30; struct list{

int v[maxlength+1]; int s; }

int count, result; void test(list &A){ int i ,j;

i=A.s; j=maxlength;

while((i

if (i

else result=1; if (result==1)

for(i=A.s; i<=maxlength; i++)

3 2 3 5 2 5 6 2 8 9 2

(a<=k) {S[c]=R[a]; a++; c++;} cout<

void add(list &A, list &B){ int i, j, x; i=A.s; x=0;

for (j=maxlength; j>=A.s j--) { x=A.v[j]+A.v[i]+x; B.v[j]=x; x=x/10; i++; }

B.s=A.s; if(x>0){

B.s--; B.v[B.x]=x; }

count++; }

void revers(list &A, list &B) {

test(A);

if((result==0)&&(count