《数据结构》试卷B

《《数据结构》试卷B》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、-、单项选择题（在每小题的四个备选答案中选出一个正确答案，并将其号码填在题干的括号内。每小题2分，共30分）1•计算机中算法是指（C）。A.计算方法B.排序方法C.解决某一问题的有限运算序列D.调度方法2.在一个单链表中，若指针p所指结点不是最后结点，在p之后插入指针s所指结点，则应执行的语句序列为（B）。A.s->next二p；p->next二s;B.s->next二p->next;p->next二s；C.s->next=p->next;p:=s;D.p->next=s;s->next=p;3.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（B）A.he

2、ad==NULLB・head->next==NULLC.head->next==headD.head!=NULL4.循环队列用数组A[0.・m-1]存放其元素值,已知其头尾指针分别是front和rear,则当前队列屮的元素个数是（A）。A.(rear-front+m)MODmB.rear-front+1C.rear-front~lD.rear-front01o11015.从邻接矩阵A=l°1可可以看出，此图共有（1）个顶点。如果是有向图,该图共有（2）条弧；(1)A、9B.3C、6D、1(2)A、5B.4C.3D.26.中缀表达式A-(B+C/D)*E的后缀形式是()A、AB

3、-C+D/E*B、ABC+D/-E*C、ABCD/E*+-D、ABCD/+E*-7.下列程序段的算法复杂度为（）s=0;while(s

4、度等于该顶点的（）。A.入度与出度之和B.出度C.入度D.入度与出度之差12.输入序列为（A,B,C,D）,顺序通过一个栈后，不可能得到的输出序列有(D)A、(A,B,C,D)B、(D,C,B,A)C、(A,C,D,B)D、(C,A,B,D)13.无向图的邻接矩阵是一个（)A.对称矩阵B.零矩阵C.上三角矩阵D.对角矩阵14.一个向量的第一个元素的存储位址为100,每个元素的长度为2个字节，则第5个元素的起始位址为（B）A、110B、108C、100D11215.设有两个串p和q,其屮q是P的子串，求q在P中首次出现的位置的算法称为（C）A.求子串B.联接C.匹配D.求串长二

5、、判断题（判断下列各题，正确的在题干后面括号内打“J”，错误的打“X”。每小题1分，共10分）1、（1）二叉树是一•种特殊结构的树。2、（1）在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。3、（）具有n个顶点的完全有向图有n*（n-l）/2条边。4、()希尔排序是一种稳定的排序方法。5、()折半查找只适用于有序表，包括有序的顺序表和有序的链表。6、(1)已知一棵叉树的先序序列和屮序序列一•定能构造出该二树。7、(0)在用单链表表示的链式队列时，队头在链表的链尾位置。8、()算法的运行时间涉及加、减、乘、除、转移、存、取、等基本运算。耍想准确地计算总运

6、算时间是不可行的。9、(1)n个结点的完全二叉树的高度为Llog2,1J+1。10、()进行折半搜索的表必须是顺序存储的有序表。三、填空题(每小题2分，共10分)1、在带冇头结点的单链表L屮，第一个点元素的指针是L->next2、在双循环表中，在指针p所指结点前插入指针s所指结点，需执行下列四个语句:s->next=p;s->prior=p->prior;p->prior=s;p->next=s->next；3、已知一棵二叉树的叶了结点数为50,一分枝结点数为30,则总结点数为129o4、深度为K的完全二叉树至少有个结点，至多有个结点。5、图的主要存储结构有两种，分别为：和o

7、四、应用题(每小题6分，共30分)1.对下图所示二叉树分别按前序、中序、后序遍历，给出相应的结点序列。2.有一份电文屮共使用五个字符：a.b、c、d、e,它们的出现频率依次为8、14、10、4、18,请构造和应的哈夫曼树(左子树根结点的权小于等于右子树根结点的权），求出每个字符的哈夫曼编码。1.下图是用邻接表存储的图，画出此图，并写出从C点开始按深度优先遍历该图的结果。（6分）2.将关键码53,78,65,17,87,09,81,45,23依次插入到一棵初始为空的二叉排序树中，画出插入关键码后的二叉排序