杭州电子科技大学数据结构期末复习卷.doc

是非题 1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系， 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。 19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所 以，二叉树是树的特殊情形。× 20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。× 二．选择题 1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中( c )具有先进先出（FIFO）特性， ( b )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’) 的结果是 ( d ) 。 a: ‘database’ b: ‘data-base’ c: ‘bas’ d: ‘data-basucture’ 5. 设有二维数组A 5 x 7 ,每一元素用相邻的4个字节存储，存储器按字节编址。 已知A的起始地址为100。则按行存储时，元素A06的第一个字节的地址是（ d ） 按列存储时，元素A06的第一个字节的地址是（ a ） a: 220 b: 200 c: 140 d: 124 6. 对广义表 A=（（a,(b)）,(c,()),d）执行操作gettail(gethead(gettail(A))) 的结果是：（ b ） 。 a:（） b: （（）） c: d d: (d) 7．假设用于通讯的电文仅由6个字符组成，字母在电文中出现的频率分别为7, 19, 22, 6, 32, 14。 若为这6个字母设计哈夫曼编码（设生成新的二叉树的规则是按给出的次序从左至右的结合，新生成的二叉树总是插入在最右），则频率为7的字符编码是（ g ），频率为32的字符编码是（ c ）。 a: 00 b: 01 c: 10 d: 11 e: 011 f: 110 g: 1110 h:1111 8. 对二叉排序树（ b ）可得到有序序列。   a:按层遍历 b:前序遍历 c:中序遍历 d:后序遍历 9．已知某树的先根遍历次序为abcdefg，后根遍历次序为cdebgfa。 若将该树转换为二叉树,其后序遍历次序为（ d ）。 a: abcdefg b: cdebgfa c: cdegbfa d: edcgfba 10．对一棵完全二叉树进行层序编号。则编号为n的结点若存在右孩子,其位序是( d )。 编号为n的结点若存在双亲,其位置是( a )。 a: n/2 b: 2n c:2n-1 d:2n+1 e:n f: 2(n+1) 11．关键路径是指在只有一个源点和一个汇点的有向无环网中源点至汇点（ c ）的路径。 a:弧的数目最多 b:弧的数目最少 c:权值之和最大 d:权值之和最小 12. 哈希表的查找效率取决于（ d ）。 a: 哈希函数 b:处理冲突的方法。 c:哈希表的装填因子。 d:以上都是 13．从逻辑上可以把数据结构分成( c )。 A. 动态结构和静态结构 B. 顺序组织和链接组织 C. 线性结构和非线性结构 D. 基本类型和组合类型 14．在计算递归函数时，如不用递归过程，应借助于( b )这种数据结构。 A. 线性表 B. 栈 C. 队列