发布时间 : 星期二 文章数据结构（本）期末综合练习（2014年12月）更新完毕开始阅读326a3983be1e650e53ea992e
期末综合练习二
一、单项选择题
1.数据的存储结构包括数据元素的表示和（ ）。
A . 数据处理的方法 B. 数据元素间的关系的表示 C . 相关算法 D. 数据元素的类型 2 .下面关于线性表的叙述中,错误的是( )。
A . 线性表采用顺序存储,必须占用一片连续的存储空间
B. 线性表采用顺序存储,进行插入和删除操作,不需要进行数据元素间的移动 C. 线性表采用链式存储，不必占用连续的存储空间
D. 线性表采用链式存储，进行插入删除操作，不需要移动元素
3．设有一个长度为22的顺序表，要删除第8个元素需移动元素的个数为（ ）。 A．15 B．22 C．14 D．23
4 .设有一个长度为28的顺序表，要在第12个元素之前插入一个元素（也就是插入元素作为新表的第12个元素），则移动元素个数为（ ）。 A．12 B．17 C. 13 D．11
5．元素2,6,10,14按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列 的不可能输出序列是是（ ）。（进栈出栈可以交替进行）。 A．14,10,6,2 B．2,6,10,14 C．14,10,2,6 D．6,2,14,10
6．元素2，4，6,8按顺序依次进栈，则该栈的不可能输出序列是（ ）（进栈出栈可以交替进行）。
A．8,6,4,2 B．2,4,6,8
C．4,2,8,6 D．8,6,2,4
7．对一个栈顶指针为top的链栈进行进栈操作，设P为指向待进栈的结点的指针，把e 的值赋值给该结点的数据域，然后使该结点进栈，则执行（ ）。 A．p->data=e; p=top->next; top=top?next; B．p->data=e;p->next=top;top=p; C．p->data=e;top=p;
D．p->data=e;p->next=top->next; top =p; 8．对一个栈顶指针为top的链栈进行出栈操作，用变量e保存栈顶元素的值 ，则执行 （ ）。
A. e= top->next; top->data=e; B．e=top->data; top=top->next; C．top=top->next; e=top->data; D．top=top->next; e=data; 9 .对不带头结点的单向链表,判断是否为空的条件是（ ）（设头指针为head）。 A．head==NULL B．head->next= =NULL
C．head->next= =head D．head =NULL
10．在一个尾指针为rear的不带头结点的单循环链表中,插入一个s所指的结点,并作为第一个结点，可执行（ ）。
A．rear?next= s; s?next=rear?next B．rear?next=s?next; C．rear=s?next D．s?next=rear?next ; rear?next=s; 11．设有一个25阶的对称矩阵A（矩阵的第一个元素为a1,1），采用压缩存储的方式，将其
下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a7,5在一维数组B中的下标是（ ）。
A．34 B．14 C．26 D．27
12．设有一个28阶的对称矩阵A（矩阵的第一个元素为a1,1），采用压缩存储的方式，将其
下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则数组中第40号元素对应于矩阵中的元素是（ ）。
A．a10,8 B．a9,4 C．a9,5
D．a8,5
13.数组a经初始化 char a[ ]=“English”; a[7]中存放的是（ ）。 A. 字符串的结束符 B. 字符h
C. 〝h〞 D. h
14.数组a经初始化 char a[ ]=“English”; a[1]中存放的是（ ）。 A. 字符n B. 字符E
C. 〝n〞 D. 〝E〞
15 .设主串为“ABcCDABcdEFaBc”，以下模式串能与主串成功匹配的是（ ）。
A. aBc B. BCd
C. ABC D .Abc 16. 程序段char a[ ]=“English”; char *p=a; int n=0;
while( *p!=‘\\0’){ n++; P++;}结果中,P指向（ ）。 A. 字符h B.a C. 字符串的结束符 D.7
17．设一棵哈夫曼树共有11个非叶结点，则该树有（ ）个叶结点。 A．22 B。10 C．11 D．12 18．在一棵二叉树中，编号为17的结点的双亲结点的的顺序编号为（ ）。 A．34 B．7 C．9 D．8 19．一棵具有38个结点的完全二叉树，最后一层有（ ）个结点。
A．7 B．5 C．6 D．8 20．设一棵采用链式存储的二叉树，除叶结点外每个结点度数都为2，该树结点中共有20个指针域为空。则该树共有（ ）个非叶子结点
A．21 B．22 C． 9 D．10
21．已知如图1所示的一个图，若从顶点V1出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。
A．V0V1V2V3V6V7V4V5V8 B．V0V1V2V3V4V5V8V6V7
C．V0V1V2V3V4V5V6V7V8 D．V0V1V2V3V4V8V5V6V7
V1 V0 V2 V3 V4 V5 V6 V7 V8
图1
22．已知如图1所示的一个图，若从顶点V0出发，按深度优先法进行遍历，则可能得到的一种顶点序列为（ ）。
A. V0V1V2V4V8V5V3V6V7 B．V0V1V2V4V5V8V3V6V7
C．V0V1V2V4V8V3V5V6V7 D．V0V1V3V6V7V2V4V5V8
23．在有序表{10,14，34，43，47，64，75，80，90}中，用折半查找法查找值80时，经（ ）次比较后查找成功。
A．4 B．2 C．3 D．5 24．对( )进行中序遍历，可以使遍历所得到的序列是有序序列。 A．完全二叉树 B．二叉排序树 C．满二叉树排 D．哈夫曼树
25．排序算法中，从尚未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行
比较，然后将其放入已排序序列的正确位置的方法是（ ）。
A．冒泡排序 B．直接插入排序 C．归并排序 D．选择排序 26．有一个长度为7的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平
均比较次数为（ ）。
A．17/7 B．18/7 C．21/7 D．20/7
27．一组记录的关键字序列为（22，55，32，14,16，60），利用快速排序，以第一个关键字
为分割元素，经过一次划分后结果为（ ）。
A．16，14，22，55，32，60 B．16，14，22，32，55，60 C．16，14，22，60，32，55 D．14，16，22，32，55，60
28．排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的一
端的方法，称为（ ）排序。
A．堆 B．冒泡 C．选择 D．快速 29．一组记录的关键字序列为（80,57,41,39,46,47），利用堆排序（堆顶元素是最小元素）的方法建立的初始堆为（ ）。
A．39，46，41,57,80，47 B．39，47，46，80，41，57
C．41，39，46，47，57，80 D．39，80，46，47，41，57 30．一组记录的关键字序列为（12，45，22，4,6，50），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（ ）。
A．6，4，12，45，22，50 B．6，4，12，22，45，50
C．6，4，12，50，22，45 D．4，6，12，22，45，50
二、填空题
1.把数据存储到计算机中,并具体体现数据之间的逻辑结构称为________结构。 2.结构中的数据元素存在一对一的关系称为________结构。 3.从一个栈顶指针为h的链栈中删除一个结点时，用x保存被删结点的值，可执行x=h->data;和________。(结点的指针域为next) 。
4.向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行________和h=s;操作。(结点的指针域为next)
5. 广义表的( a , d , e , (i ,j ) ,k )表尾是________ 。 6.广义表的( a , a ,b , d , e ,( (i ,j ) ,k ) )表头是_____ __。
7.广义表的(( a,c) , a ,b , d , e ,( (I ,j ) ,k ) )表头是________。 8. 广义表的( (a,c) , d ,( e ,i ,j ,k ) )表尾是_____ ___ 。 9. 设顺序队列的类型为typedef struct
{ ElemType data[MaxSise]; int front,rear;
}Squeue; Squeue *sq;
sq为指向顺序队列的指针变量，要进行元素的出队操作，并把元素赋给变量x, 按教课书约定,可用语句x=sq->data[sq->front];和________。 10. 设顺序队列的类型为typedef struct
{ ElemType data[MaxSise]; int front,rear;
}Squeue;
Squeue *sq;
sq为指向顺序队列的指针变量，要进行新元素x的入队操作，按教科书约定,可用语句 sq->data[sq->rear]=x;和________ 。
11. 对20个元素的序列用冒泡排法进行排序，第5趟冒泡共需要进行________次元素间的比较。 12.对16个元素的序列用冒泡排法进行排序，共需要进行________趟冒泡。 13. 在对一组记录（5,7,3,1,2,6,4,10,9,8,16,13,18,17））进行直接插入排序 (由小到大排序)， 当