21秋西电网院数据结构模拟试题5题目及答案
西安电子科技大学网络教育2015学年期末模拟试题5课程名称：__数据结构 考试形式： 闭 卷 学习中心：_________ 考试时间：90分钟姓 名：_____________ 学 号： 一 填空题（每空1分，合计20分）
栈是一种_____________的线性表，队列是一种_____________的线性表(要求填特性)。
具有354个结点的完全二叉树深度为 ________________，树中度为1的结点数为______________。
数组的运算有______________________________________ 和____________________________。
稀疏矩阵的压缩存储一般采用_____________________________存储方式。
广义表运算： tail ((( a, b ), ( c, ( d, e )))) = _______________________。
数据结构中评价算法的两个重要指标是__________ 、__________。
一个算法具有5个特性: 、 、 ，有零个或多个输入、有一个或多个输出。
已知指针p指向单链表L中的某结点，则删除其后继结点的语句是: 。
n个顶点的连通图的生成树含有______条边。
顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为____次；当使用监视哨时，若查找失败，则比较关键字的次数为____。
若不考虑基数排序，则在内排序过程中，主要进行的两种基本操作是关键字的 __________ 和记录的 _________ 。
直接插入排序用监视哨的作用是___________________。二 单项选择（每题2分，合计30分）
1. 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ ）。
A．CBEFDA B． FEDCBA C． CBEDFA D．不定
2. 具有12个关键字的有序表，折半查找的平均查找长度（ ）
A. 3.5 B. 4 C. 2.5 D. 5
3. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。
A.LL B. LR C.RL D.RR
4．设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )
A．8 B．3 C．5 D．9
5. 若完全无向图有n 个顶点，则边的数目为（ ）：
A. n B. n-1
C.n(n-1)/2 D. n(n-1)
6. 就平均性能而言，目前最好的内排序方法是( )排序法。
A. 冒泡 B.希尔插入 C.交换D. 快速
7．哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行( )次探测。
A． k B. k+1 C. k(k+1)/2 D.1+k(k+1)/2
8．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )
A．（100，80， 90， 60， 120，110，130）
B.（100，120，110，130，80， 60， 90）
C.（100，60， 80， 90， 120，110，130）
D. (100，80， 60， 90， 120，130，110)
9. 二叉查找树的查找效率与二叉树的( )有关。
A. 高度 B. 结点的多少 C. 树型 D. 结点的位置
10. 下面哪一方法可以判断出一个有向图是否有环（回路）:( )
A．深度优先遍历 B. 拓扑排序
C. 求最短路径 D. 广度优先遍历
11. 当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 A中时，数组中第i个结点的左孩子为（ ）
A．A(2i=<n)B. A(2i+1=< n)C．AD．无法确定
12. 下面的说法中正确的是（ ）.
（1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变；
（2）按二叉树定义，具有三个结点的二叉树共有6种。
A．(1)(2) B．(1) C．(2) D．(1)、(2)都错
13. 在完全二叉树中，若一个结点是叶结点，则它没（ ）。
A．左子结点 B．右子结点
C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点
14. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )。
A. 0 B. 1 C. 2 D. 不确定
15. 下列哪一种图的邻接矩阵是对称矩阵？（ ）
A．有向图 B．无向图 C．AOV网 D．AOE网三 应用题（每题6分 合计36分）
比较顺序存储和链式存储的优缺点。
简述平衡二叉树特点及其平衡调整规律方法。
写出右图二叉树的先序、中序、后序遍历序列。
除留余数法对给定关键字（10，8，17，16，4，7，25，18）进行哈希制表，地址空间为0～9，以除留余数法构造哈希函数，线性探查法解决冲突，画出哈希表并计算查找成功的平均查找长度。写出用直接插入排序对关键字序列（53,24,45,64,51,24,95,36）进行排序的每一趟结果。假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成。它们在电文中出现的频度分别为{0.31,0.16,0.10,0.08,0.11,,0.20,0.04},
1) 为这7个字母设计哈夫曼编码；
2）对这7个字母进行等长编码，至少需要几位二进制数？哈夫曼编码比等长编码使电文总长压缩多少？
四 编程题（每题7分 合计14分）
写出直接插入排序的类C语言算法。
试写出在单链表La中删除第i个结点的类C语言算法。
页:
[1]