2017年电大本科《数据结构（本）》期末复习试题及答案
一、单项选择题
1．栈和队列的共同特点是（）。
A.元素都可以随机进出B.都是先进先出 C.都是先进后出D.都是操作受限的线性结构 2.数据的存储结构包括数据元素的表示和（）。 A.数据处理的方法B.数据元素间的关系的表示 C.相关算法D.数据元素的类型
3．对一个栈顶指针为top的链栈进行入栈操作，通过指针变量p生成入栈结点，则执行：p=(structnode*)malloc(sizeof(structnode);p->data=a;和（）。 A.top->next=p;p=top;B.p->nex=top;top=p; C.top=top->next;p=top;D.p->next=top;p=top;
4．树状结构中数据元素的位置之间存在（）的关系。
A．每一个元素都有一个直接前驱和一个直接后继B．一对一 C．多对多D．一对多
5．设头指针为head的非空的单向链表,指针p指向尾结点,则通过以下操作() 可使其成为单向循环链表。 A．p->next=NULL;B．head=p; C．p->next=head;D．p=head;
6．设有一个长度为26的顺序表，要插入一个元素,并使它成为新表的第6个元素,需 移动元素的个数为（）。 A．21B．22C．20D．19 7．一种逻辑结构（）。
A．只能有唯一的存储结构B．可以有不同的存储结构
C．与存储该逻辑结构的计算机相关D．是指某一种数据元素的性质
8．头指针为head的带头结点的单向循环链表，p所指向尾结点，要使该链表成为 不带头结点的单向循环链表,可执行head=head->nex;和（）。 A．p=head->nextB．head->next=p
C．head->next=p->nextD．p->next=head;
9．把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。 A．存储结构B．逻辑结构
C．数据元素的存储D.给数据元素分配存储空间
10．元素111，113，115，117按顺序依次进栈，则该栈的不可能输出序列是（）（进 栈出栈可以交替进行）。
A．117，115，113，111B．111，113，115，117 C．117，115，111，113D．113，111，117，115
11．图状结构中数据元素的位置之间存在（）的关系。 A．一对一B．一对多
C．多对多D．每一个元素都有一个且只有一个直接前驱和一个直接后继 12．以下说法正确的是（）。 A．栈的特点是先进先出 B．栈的特点是先进后出
C．队列的特点是先进后出
D.栈和队列的特点都是后进后出
13．一个单链表中,在p所指结点之后插入一个s所指的结点时，可执行: s->next=p->next;和（）。
A．s=p->next;B．p->next=s->next; C．p=s->next;D．p->next=s;
14.设有一个20阶的对称矩阵A(第一个元素为a1,1)，采用压缩存储的方式，将其下三 角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵元素a6,2 在一维数组B中的下标是（）。 A．21B．28C．17D．23
15．元素12，14，16，18顺序依次进栈，则该栈的不可能输出序列是（）。 （进栈出栈可以交替进行）。
A．18，16，14，12B．12，14，16，18 D．14，12，18，16D．18，16，12，14 16．设有串p1=”ABADF”,P2=”ABAFD”，P3=”ABADFA”,P4=”ABAF”,以下四个串中最大的是()。
A．p3B．p2C．p1D．p4
17．设有一个30阶的对称矩阵A(第一个元素为a1,1)，采用压缩存储的方式，将其 下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元 素a9,2在一维数组B中的下标是（）。 A．41B．32C．18D．38
18.数组a经初始化chara[]=“English”;a[7]中存放的是（）。 A.字符串的结束符B.字符h C.〝h〞D.变量h
19．设有一个长度为32的顺序表，要删除第8个元素需移动元素的个数为（）。 A．15B．22C．14D．24
20.设主串为“ABcCDABcdEFaBc”，以下模式串能与主串成功匹配的是（）。 A.BcdB.BCdC.ABCD.Abc
21.在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（）。 A．2iB．2i-1C．2i+1D．2i+2
22．在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为（）。 A．2i+1B．2i-1C．2iD．2i+2
23．一棵具有16个结点的完全二叉树，共有（）层。(设根结点在第一层) A．7B．6C．4D．5
24．如图1所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得 到的一种顶点序列为（）。
A．abecdfB．aebcfdC．aecbdfD．aedfcb
25．如图2所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得 到的一种顶点序列为（）。
A．abecdfgB．acfebgdC．aebcfgdD．aedfcgb
26．线性表以（）方式存储，能进行折半查找。 A．链接B．顺序C．关键字有序的顺序D．二叉树
27.字符串“DABcdabcd321ABC”的子串是()。 A.“cd32”B.“ABcD” C.“aBcd”D.“321a”
28．一棵具有38个结点的完全二叉树，最后一层有（）个结点。 A．7B．5C．6D．8
29．如图3所示，若从顶点a出发，按广度优先搜索法进行遍历，则可 能得到的一种顶点序列为（）。
A．abcdfgeB．abcdfegC．acbfedgD．abcfgde
30.下图4的拓扑序列是()。 A．52346B．23645 C．56234D.23564
二、填空题
1.对稀疏矩阵进行压缩存储,可采用三元组表，一个有10行的稀疏矩阵A共有97个 零元素，其相应的三元组表共有3个元素。该矩阵A有列。 2．结构中的数据元素存在多对多的关系称为________结构。
3．在单向链表中，q指向p所指结点的直接后继结点，要删除q所指结点，可以用 操作______=q->next;。
4.n个元素进行冒泡法排序，第j趟冒泡要进行______次元素间的比较。
5.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行下标、列下标和_______三项信息。
6．中序遍历________树可得到一个有序序列。 7.队列的操作特点是后进________。
8.待排序的序列为8,3,4,1,2,5,9,采用直接选择排序算法,当进行了两趟选择后,结果序列为()。 9．n个元素进行冒泡法排序，通常需要进行________趟冒泡。 10广义表((a,b),d,e,((i,j),k))的长度是________。
11．中序遍历二叉排序树可得到一个________的序列。 12.广义表的(c，a,(a,b),d,e,((i,j),k))深度是________。 13.广义表(c,a,(a,b),d,e,((i,j),k))的长度是________。
14.对稀疏矩阵进行压缩存储,可采用三元组表，一个有10行10列的稀疏矩阵A共有95个零元素，其相应的三元组表共有个元素。
15.广义表的(c,a,(a,b),d,e,((i,j),k))深度是________。
16．在对一组记录(50,49,97,22,16,73,65,47,88)进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较_________次。
17.循环队列在规定少用一个存储空间的情况下，队空的判定条件为________。 18.一棵有5个叶结点的哈夫曼树,该树中总共有_____个结点。 19.c语言中,字符串“E”存储时占个字节。
20.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有_______个结点。 （根所在结点为第1层）。
21．一棵二叉树中有n个非叶结点，每一个非叶结点的度数都为2，则该树共有_______ 个叶结点。
22．设有一个长度为40的顺序表，要删除第8个元素需移动元素的个数为_______。23．在
对一组记录(55,39,97,22,16,73,65,47,88)进行直接插入排序时，当把第7个记录65 插入到有序表时，为寻找插入位置需比较_________次。 24.有以下程序段 chara*+=“English”; char*p=a;intn=0;
while(*p!=‘\\0’){n++;p++;}结果中，n的值是_______。 三、综合题
1．设查找表为(1,10,11,14,23,27,29,55,68),元素的下标依次为1,2,3,??，9。 （1）画出对上述查找表进行折半查找所对应的判定树（树中结点用下标表示）。 （2）说明成功查找到元素14,需要依次经过与哪些元素的比较？共几次比较？ （3）求在等概率条件下，成功查找的平均比较次数？ .
2．有一个长度为11的有序表(1,2,11,15,24,28,30,56,69,70,80),元素的下标依次为 1,2,3,??,11，按折半查找对该表进行查找。
(1）画出对上述查找表进行折半查找所对应的判定树。
（2）说出成功查找到元素56,,需要依次经过与哪些元素的比较？ （3）说出不成功查找元素72,需要进行元素比较的次数？ 3．
(1)以3，4，5，8，9，作为叶结点的权，构造一棵哈夫曼树。 (2)给出相应权重值叶结点的哈夫曼编码。
(3)n个叶结点的哈夫曼树，总共有多少个结点？
4.(1)一组记录的关键字序列为（57，90，67，50，51，56），利用堆排序（堆顶元素是最小元素）的方法建立初始堆（要求以完全二叉树描述）。
(2)对关键字序列(56,51,71,54,46,106)利用快速排序，以第一个关键字为分割元素， 给出经过一次划分后结果。
(3)一组记录的关键字序列为（60,47，80，57，39，41，46,30），利用归并排序的方法,分别给出(1,1)归并、(2,2)归并、(4,4)归并的结果序列。 四、程序填空题
1．以下是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、 右指针域分别为left和right，数据域data为字符型，BT指向根结点）。 voidInorder(structBTreeNode*BT) {
if(BT!=NULL){ （1）; （2）;
Inorder(BT->right);} }
利用上述程序对右图进行遍历，结果是（3）;
2.设线性表为（16，20，26，24），以不带头结点的单向链表存储，链表头指针为head,以下程序的功能是输出链表中各结点中的数据域data。 structnode {intdata;
structnode*next;
};
typedefstructnodeNODE; #defineNULL0 voidmain()
{NODE*head,*p;
p=head;/*p为工作指针*/ do
,printf(“%d\\n”,___(1)_____); ___(2)_____;
}while(___(3)_____); }
3．以下冒泡法程序对存放在a[1]，a[2]，??，a[n]中的序列进行排序，完成程序中的空格部分，其中n是元素个数，要求按升序排列。 voidbsort(NODEa[],intn) {NODEtemp; inti,j,flag;
for(j=1;（1）;j++); {flag=0;
for(i=1;（2）;i++) if(a[i].key>a[i+1].key) {flag=1; temp=a[i];
（3）; （4）; }
if(flag==0)break; } }
设有序列6，4，5，8，2，1，给出由该程序经过两趟冒泡后的结果序列（5）
4.以下函数为直接选择排序算法，对a[1],a[2],?a[n]中的记录进行直接选择排序，完成 程序中的空格 typedefstruct {intkey; ?? }NODE;
voidselsort(NODEa[],intn) {
inti,j,k;
NODEtemp;
for(i=1;i<=___(1)_____;i++) {
k=i;
for(j=i+1;j<=(2)_____;j++)
if(a[j].key
if(i!=k) {
temp=a[i]; (4)_____; (5)____; } } }
练习一答案 一、单项选择题
1．C2．B3．B4．D5．C6．A7．B8．D9．A10．C11．C12．B13．D14．C15．D16．B17．D18．A19．D20．A21.C22．C23.D24．C25.D26．C27.A28．A29.A30．C 二、填空题 1．10 2．图状 3．p->next; 4．n-j
5．数组元素 6．二叉排序树 7．后出
8．1，2，4，8，3，5，9 9．n-1 10．4 11．有序 12．3 13．6 14．5 15．3 16．3
17.front==rear
18．9 19.2 20.12 21.n+1 22．32 23.3 24．7
三、综合题 1． (1)
(2)按序号5,2,3,4。按元素23，10，11，144次 (3)ASL=(1+2*2+3*4+4*2)/9=25/9 2． (1)