华东交通大学数据结构试卷.docVIP

华东交通大学2011—2012学年第一学期考试卷 　　　　　　　　　　　　　　　　　　　 　试卷编号：　　　　（ A ）卷 数据结构 课程 课程类别：必 闭卷 　　 考试日期： 2012.1 题号 一 二 三 四 五 六 七 八 九 十 总分 累分人签名 题分 20 30 42 8 100 得分 考生注意事项：1、本试卷共 4 页，总分　100　分，考试时间　120　分钟。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。 3、答案必须写在答题纸上，考试结束时请将答题纸与试卷分开上交，试卷、答题纸、草稿纸都必须交回。 得分 评阅人 一、选择题(每题 2 分，共 20 分) 　　 1. 计算机算法必须具备输入、输出（ ）5个特性。 A．可行性、可移植性和可扩充性 B. 有穷性、确定性、可行性 C. 确定性、有穷性和稳定性 D. 可读性、稳定性和安全性 2.在长度为n的顺序表的第i个元素（1=i=n）之前插入数据元素时，需向后移动（ ）个元素。 A．n-i+1 B. n-i C. i D. n 3. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ 　 ）。 A．p-next=s; s-next=p-next; B．s-next=p-next; p-next=s; C．p-next=s; p-next=s-next; D. p-next=s-next; p-next=s; 4. 判别表达式中左、右括号是否配对出现的算法，采用（ ）数据结构最佳。 A．队列 B．线性表 C．栈 D．双向链表 5．包含2012个顶点的连通图最少有（ ）条边。 A. 2011 B. 2012 C. 2013 D. 2014 6. 在有序表{4，15，26，27，38，64，81}中折半查找38的比较次数为（ ）。 A．1 B．2 C．3 D．4 7. 线索链表中，若结点p的RTag=1，则p-rchild指向（ ）。 A. 左孩子 B. 右孩子 C. 前驱 D. 后继 8. 对完全二叉树按层序从1开始编号，编号为100的结点是编号为50的结点的（ ）。 A. 左孩子 B. 右孩子 C. 双亲 D. 根结点 9．下图AOE网络中，要完成该工程需要（ ）时间。 A. 43 B.18 C. 31 D. 35 10．顺序查找的时间复杂度为（ ） A． O(n/2) B．O(n) C．O(1) D．O(log2n) 得分 评阅人 二、填空题(每题 2 分，共 30 分) 1．数据结构中评价算法的两个重要指标是算法的 (1) 和空间复杂度。 2. 链接存储的特点是利用 (2) 来表示数据元素之间的逻辑关系。 3. 假设有5行4列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A[0][0]的地址为1000，按行优先存储时元素A[2][3]的地址是 (3) 。 4．带头结点的单链表L中，L-next-next表示第 （4） 个数据元素。 5．若用一个大小为8的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear的值为 (5) ，front的值为 (6) 。 6. SubString(‘HAPPYNEWYEAR’, 6, 3）= （7） 。 7．一棵具有267个结点的完全二叉树，它的深度为 (8) ，有 (9) 个叶子结点。 8．以下代码片段中，k++的执行次数为 (10) 。 for (int i=0; in; i++) for (int j=0; jn; j++) k++; 9．若一棵二叉树具有7个度为2的结点，3个度为1的结点，则度为0的结点个数是_ (11) 。 10．右图的一个拓扑排序序列为A （12） EF。 11. 带头结点的循环链表中最后一个结点的指针域指向 （13） 。 12. 顺序表第 (14) 个数据元素的存储位置称为基地址。