资源描述：
《08_09 数据结构试卷b》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、一、填空题（每空1分，共18分）1、设一棵完全二叉树有1000个结点，则此完全二叉树有_______个叶子结点，有______个度为2的结点，有______个度为1的结点。2、单循环链表L中指针P所指结点为尾结点的条件为_________。3、有一个8×8的下三角矩阵A，若采用行序为主序顺序存储于一维数组a[1...N]中，则N的值为_________。4、用带头结点的循环链表表示的队列,若只设尾指针rear,则队空的条件是____________。5、n个顶点的连通无向图至少有_____________条边，至多有_____________
2、__条边。6、稀疏矩阵的压缩存储方式有十字链表和__________。7、广义表(a,(a,b),d,e,((i,j),k))的长度是______，深度是_______。8、如果T1是由树T转换而来的二叉树，那么T中结点的后序遍历序列就是T1中结点的________遍历序列。9、在顺序表(3,6,8,10,12,15,16,18,21,25,30)中，用折半法查找关键码值11，所需的关键码比较次数为__________。10、已知模式串T=¢abcdabcd¢，则其next数组值为_____________。11、设栈S和队列Q的初始状态为空
3、，元素a,b,c,d,e,f,g依次通过栈S，一个元素出栈后即进入队列Q。若这7个元素出队列的顺序是c,e,f,d,b,g,a，则栈S至少可以同时容纳______个元素。12、表达式求值是_______应用的一个典型例子。13、________排序方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。14、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为________________（使用大O标记）。二、选择题（每题1分，共10分）1、二叉树是非线性数据结构，所以___________
4、____。A.它不能用顺序存储结构存储B.它不能用链式存储结构存储C.顺序存储结构和链式存储结构都能存储D.顺序和链式存储结构都不能使用2、关键路径是事件结点网络中_______。A.从开始结点到完成结点的最长路径B.从开始结点到完成结点的最短路径C.最长的回路且按拓扑排序D.最短的回路3、排序方法中，从未排序序列中挑选最大（或最小）元素，并将其依次放入已排序序列（初始为空）的一端，其方法称为_______。A.插入排序B.归并排序C.选择排序D.快速排序4、广义表G=（(a,b,c)，（d，e,f））运用head和tail函数取出G中原子e
5、的运算是_______。A.head(tail(G))B.tail(head(G))C.head(tail(head(tail(G))))D.head(tail(tail(head(G))))5、对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为_________。A顺序表B用头指针表示的单循环链表C用尾指针表示的单循环链表D单链表6、假设以第一个元素为分界元素，对字符序列（Q,H,C,Y,P,A,M,S,R,D,F,X）进行快速排序，则第一次划分的结果是__________。A(A,C,D,F,H,M,P,Q,R,S,X,Y)B(A
6、,F,H,C,D,P,M,Q,R,S,Y,X)C(F,H,C,D,P,A,M,Q,R,S,Y,X)D(P,A,M,F,H,C,D,Q,S,Y,R,X)7、假定有k个关键字互为同义词，若用线性探测法把这k个关键字插入哈希表中，至少要进行_________次探测。A.k-1B.kC.k+1D.k(k+1)/28、已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该_______。A．将邻接矩阵的第i行删除B.将邻接矩阵的第i行元素全部置为0C.将邻接矩阵的第i列删除D.将邻接矩阵的第i列元素全部置为09、以下哪一个不是队列的基本运算
7、？____________A.从队尾插入一个新元素B.从队列中删除第i个元素C.判断一个队列是否为空D.读取队头元素的值10、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为___________。A、48B、49C、50D、51三、应用题（每小题9分，共36分）1、关键码集合如下：{10，2，13，15，12，14}，用堆排序方法从小到大排序，堆排序的初态如图1所示，画出建堆和重建堆的过程。10131213142图12、给出图2所示有向图G的邻接表表示，按Dijk
8、stra算法，给出由V0到其余各顶点的最短路径。（参考表1中”i=1”的各项填写，对于已求出最短路径的顶点则不用重复填写）20V4V5V0V2V3V11001056
