资源描述：
《黑龙江大学数据结构考试卷》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、ZP选择题（共13题，每题2分）1、一个三元组表用于表示一个（)A.线性表B.广义表C.双向链表D.稀疏矩阵2、允许对队列进行的操作有（)A.删除队首元素B.取出最近进队的元素C.在最早入队元素之前插入元素D.排序3、设广义表上L二（a,（（（f,g）,e）,（c,d）））,则表达式Tail（Head（Tail（L）））的值为（）。A.（d）B.（e）C.gD.e4、假设8行10列的二维数组a[l-8,1-10]分别以行序和以列序为主序顺序存储时，其首地址相同，那么以行序为主序时元素a[3,5]的地址与以列为主序时元素
2、（）的地址相同。A.a[5,3]B.a[&3]C.a[l,4]D.以上都不对5、深度为5的满二叉树共有（）个分支结点。A.32B.15C.30D.316、若树T有a个度为1的结点，b个度为2的结点，c个度为3的结点，则该树有（）个叶子结点。A.l+2b+3cB.a+2b+3cC.2b_3cD.l+b+2c7、若二叉树T的前序遍历序列和中序遍历序列分别是：b,d,c,a,e,f和c,d,e,a,b,f,则其后序遍历序列是（）oA.c,e,a,d,f,bB.f,e,a,c,d,bC.e,a,c,d,f,bD・以上都不对8、
3、边数很多的稠密图，适宜用（）表示。A.邻接矩阵B.邻接表C.逆邻接表D.邻接多重表9、对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。A.3B.4C.5D.610、查找哈希表，不会发牛冲突的哈希函数是（）A.除留余数法B.伪随机探测再散列法C.直接地址法D.线性探测再散列法11、对有序单链表使用（）查找法进行查找。A.折半B分块C.哈希D.顺序)D.0(n2))12、直接插入排序在最好情况下的时间复杂度为（A.0（log2n）B.0（n）C.0（nlog2n）13、以下排序方法屮所需辅助空间最大
4、的是（A.直接插入排序B.堆排序C.归并排序D.希尔排序）。一、填空题（共14个空，每空1分）1、在单链表中设置头结点的作用是（2、设环形队列存放在数组q中，数组q的长度为n,下标从0〜「1。队头指针head指向队头结点，队尾指针tail指向队尾结点后一个空闲结点。环形队列的队空标志为（）,队满标志为（），该队列的长度为（）。3、设有算术表达式x+a*（y-b）-c/d,该表达式的前缀表示为（）,后缀表示为（）o4、对关键码序列FBJGEAIDCH进行升序排列，则堆排序时，初始建堆结果的序列为（）。设关键码序列中有n个
5、元素，则堆排序的平均执行时间为（）。5、有n个顶点的有向强连通图最多有（）条边，最少有（）条边。6、在m阶树中，除了根和叶子外，每个结点的子结点数目的范围在（）之间，同时，具有k个子结点的非叶结点含有（）个键值。而在m阶B+树中，具有k个子结点的结点含有（）键值。7、G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。三、•判断对错题（共5题，每题1分）1、数据的逻辑结构与数据元素本身的形式和内容无关。（）2、哈夫曼树的所有子树也均是哈夫曼树。（）3、线性表的逻辑顺序总与其物理顺序一致。（）4、理想情况下散列表
6、等概率查找成功的平均查找长度是0（1）o（）5、求n个数中最大的k（k«n个）数，起泡排序比直接选择排序要好。（）四、应用题（共6道题，1-3题4分，4-6题6分，总分为30分）1、有5个元素，其入栈次序为A,B,C,D,E,在各种可能的出栈序列屮，第一个岀栈元素为C且第二个岀栈元素为D的岀栈序列有哪几个？2、以下表顺序建立二叉排序树，并求在等概率情况下查找成功的平均查找长度。（90,60,20,50,40,30,10,110,100,70,120,80）3、求一个有向无环图的拓扑序列时，其结果为何不唯一？4、假设用于
7、通信的电文仅由8个字母组成，字母在电文屮出现的频率为0.07.0.19、0.02、0.06、0.32、0.03、0.21、0.10。试为这8个字母设计哈夫曼编码。使用等长编码表示电文是另一种编码方案。比较两种方案的优缺点。5、已知带权无向图，利用克鲁斯科尔（Kruskal）算法，画出该无向最小牛成树的每一步。996、对一组关键字：26,5,37,1,62,11,59,15采用快速排序方法进行排序,用第一关键字做划分元素，请写出每趟划分的结果。五、•算法设计题（共3道题，1题7分2题8分3题10分，共25分）1、设n个十
8、进制整数已存入数组A[n]中，请利用栈技术，写出将A[n]中个数据转换成八进制数并存入数组的算法。2、已知（mo,・・・,「）是一个小堆顶，试写一算法，使得增加一个元素后,（7,r2,…,rn,rn_!）仍是一个堆。3、设有以标准形式存储的二叉数T,分别计算T的深度和宽度。（注：空的二叉树的深度为T,非空的二叉树的深度为其左、右子
