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

1、 名签生学 号学 级班 业专 。果后切一的起引此由担承愿，位学士学予授不将分处上以及过记到 受弊作因和籍学除开被将者考人他代或考代人他请道知还，性重严的弊作、纪违试考道知，律纪场考守遵格严将我：诺承华东交通大学2012012学年第一学期考试卷数据结构课程闭卷一、选择题（每题2分，共20分）课程类别：必题号一二三四五六七八九十总分累分人签名题分2030428100得分考生注意事项：1、本试卷共 4 页，总分 100分，考试时间120分钟。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。3、答案必须写在答题纸上，考试结束时请将答题纸与试卷分开上交，试卷、答题纸、草稿纸 都必须交回。）5个特

2、性。B.有穷性、确定性、可行性D.可读性、稳定性和安全性试卷编号： （ A ）卷考试日期：2012.11 .计算机算法必须具备输入、输出（A,可行性、可移植性和可扩充性C.确定性、有穷性和稳定性2 .在长度为n的顺序表的第i个元素（1<=i<=n）之前插入数据元素时，需向后移动（）个元素。A. n-i+1B. n-iC. iD. n3 .在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）A. p->next=s; s->next=p->next;B. s->next=p->next; p->next=s;C. p->next=

3、s; p->next=s->next;D. p->next=s->next; p->next=s;4 .判别表达式中左、右括号是否配对出现的算法，采用（）数据结构最佳。A.队列B.线性表C.栈D.双向链表5 .包含2012个顶点的连通图最少有（）条边。A.2011B.2012C.2013D.20146 .在有序表4, 15, 26, 27, 38, 64, 81中折半查找38的比较次数为（）。A. 1B. 2C. 3D. 47 .线索链表中，若结点p的RTag=1,则p->rchild 指向（）。A.左孩子B.右孩子 C. 前驱 D. 后继8 .对完全二叉树

4、按层序从1开始编号，编号为100的结点是编号为50的结点的（）A.左孩子B. 右孩子C.双亲D.根结点)时间。D. 3510.顺序查找的时间复杂度为()得分评阅人D . O(log2n)A. O(n/2) B . O(n) C .0(1)二、填空题(每题2分，共30分)1 .数据结构中评价算法的两个重要指标是算法的(1)和空间复杂度。2 .链接存储的特点是利用(2)来表示数据元素之间的逻辑关系。3 .假设有5行4列的二维数组A,每个元素占用6个字节，存储器按字节编址。已知 A00的地址为1000,按行优先存储时元素 A23的地址是(3)。4 .带头结点的单链表L中，L->next->

5、;next表示第 (4) 个数据元素。5 .若用一个大小为8的数组来实现循环队列，且当前rear和front的值分别为0和3,当从队 列中删除一个元素，再加入两个元素后，rear的值为(5), front的值为(6)。6 . SubString( ' HAPPYNEWYEAR6, 3 )=。7. 一棵具有267个结点的完全二叉树，它的深度为(8),有(9) 个叶子结点8 .以下代码片段中，k+的执行次数为 (10)for (int i=0; i<n; i+)for (int j=0; j<n; j+)k+;9 .若一棵二叉树具有7个度为2的结点，3个度为1的结点，则 度为0

6、的结点个数是 (11)。10 .右图的一个拓扑排序序列为 A (12)EF。11 .带头结点的循环链表中最后一个结点的指针域指向(13)。12 .顺序表第(14)个数据元素的存储位置称为某地址。13 .具有3个结点的二叉树有(15)种不同形态。得分评阅人三、综合题(每题6分，共42分)1.进栈顺序为12345,问能否得到45231和32451的出栈序列J?以push (X) 表示进栈和以pop (X)表示出栈的操作序列，说明为什么不能或如何能得到。第6页共4页2 .已知一棵二叉树的后序序列为 IGDBEHFCN序序歹【为DIGBAECFHft接画出此二叉树并画出 对应的森林。3.用教材中给出的

7、数值转换算法将十进制数 化情况。2012转换成八进制数，并画出转换过程中栈的变05 .假设用于通信的电文由6个字母A,B,C,D,E,F组成，字母在电文中出现的频率分别为0.17,0.12, 0.05, 0.28, 0.35, 0.03。试为这6个字母设计哈夫曼树（权值小的作为左子树）。6 .记录的关键字序列为：56, 90, 27, 67, 56, 10, 88,试构造一棵二叉排序树，并写出其构 造过程。7 .利用迪杰斯特拉算法依次求出下图中从顶点 v0到其他各顶点间的最短路径。得分评阅人四、算法题（共8分）1.实现带头结点的单链表L中，删除第i个元素，并由e返回其值（1）用编程语言定义单链表的存储结构（3分）（2）用编程语言定义函数实现上述功能（5分）华东交通大学2012012学年第一学期考试卷:名签生学题号一二三四五六七八九十总分累分人签名题分2030428100得分数据结构课程 闭卷试卷编号：（A ）卷课程类别：必考试日期： 2012.1r 种;1 抖11 fl2345678910|-| 田工 上 A1 -一,门大选择题（每题2分，共20分）果后切受弊作因和籍学除开被将者考人他代或考代人他请道知还1123456789101112131415级 班,二、填空题（每空,广2分，共30分）三、综合题（每题6分，共42分）1、业 专一的起引此由担承愿，位学士学予授不将