承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。 华东交通大学2011—2012学年第一学期考试卷
专业 班级 学号 学生签名：
试卷编号： （ ）卷
数据结构（C） 课程 闭卷 题号 一 题分 20 得分 二 30 三 42 四 8 五 六 七 八 九 课程类别：必
考试日期： 2012.1 十 总分 累分人签名 100 考生注意事项：1、本试卷共 3 页，总分 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的LTag=1，则p->rchild指向（ ）。 A. 左孩子 B. 右孩子 C. 前驱 D. 后继
8. 对完全二叉树按层序从1开始编号，编号为100的结点是编号为50的结点的（ ）。 A. 左孩子 B. 右孩子 C. 双亲 D. 根结点
第 1 页 共4页
9．下图AOE网络中，要完成该工程需要（ ）时间。
221046141961531155A. 43 B.18 D. 35
10．顺序查找的时间复杂度为（ ）
A． O(n/2) B．O(n) C．O(1) D．O(log2n)
C. 31
二、填空题(每题 2 分，共 30 分)
1．数据结构中评价算法的两个重要指标是算法的 (1) 和空间复杂度。 2. 链接存储的特点是利用 (2) 来表示数据元素之间的逻辑关系。
得分 评阅人 3. 假设有5行4列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A的基地址为1000，按行优先存储时元素A[2][3]的地址是 (3) 。（行列下标均从0开始？） 4．9阶对称矩阵采用压缩存储占用___(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; i 9．若一棵二叉树具有7个度为2的结点，3个度为1的结点，则度为0的结点个数是_ (11) 。 10．右图的一个拓扑排序序列为A （12） EF。 11. 循环链表中最后一个结点的指针域指向 （13） 。（有头结点吗？） 12. 顺序表第 (14) 个数据元素的存储位置称为基地址。 13. 具有3个结点的二叉树的有 （15） 种不同形态。 填空题10图 DFBACE三、综合题 （每题6分，共42分） 1．进栈顺序为12345，问能否得到45231和32451的出栈序列，以push（X）表示进栈和以pop（X）表示出栈的操作序列，说明为什么不能得到或如何能得 第 2 页 共4页 得分 评阅人 到。 2. 已知一棵二叉树的后序序列为IGDBEHFCA,中序序列为DIGBAECFH,直接画出此二叉树并画出对应的森林。 3. 用数值转换算法将十进制数2012转换成八进制数，并画出转换过程中栈的变化情况。 （这个算法是什么？就是书上那个例题的算法吗？） 4．已知一个无向图的邻接表 1）画出该无向图。(4分) 2）根据邻接表，写出用广度优先遍历算法从结点v0开始遍历该图得到的遍历序列。（2分） 01234567V0V1V2V3V4V5V6V72300123134517654^ ^ 76^ ^ ^ 6^ ^ 7^ 5．给定下列网G: A412B920C12158E 用克鲁斯卡尔算法找出网G的最小生成树，并画出构造过程中每一步的逻辑结构图。（6分） 5．假设用于通信的电文由6个字母A,B,C,D,E,F组成，字母在电文中出现的频率分别为0.17, 0.12, 0.05, 0.28, 0.35, 0.03。 试为这6个字母设计哈夫曼树（权值小的作为左子树）。 第 3 页 共4页 6FG10D 6．记录的关键字序列为：56，90，27，67，55，10，88，27，42，45，56，86,试构造一棵二叉排序树，并写出其构造过程。 7．利用迪杰斯特拉算法求下图中从顶点v0到其他各顶点间的最短路径，写出其执行算法过程中各步的状态。（6分写详细步骤，那么多结点，是不是太耗时间了？我觉得题量有点大，是不是可以简化这题？） 065220736452183171763214 四、算法题 （共8分） 1. 实现带头结点的单链表L 中，删除第i个元素，并由e返回其值。 （1）用编程语言定义单链表的存储结构（3分） （2）用编程语言定义函数实现上述功能（5分） 得分 评阅人 第 4 页 共4页 承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。 华东交通大学2011—2012学年第一学期考试卷 专业 班级 学号 学生签名： 试卷编号： （ ）卷 数据结构（C） 课程 课程类别：必 闭卷 考试日期： 2012.1 题号 一 二 三 四 五 六 七 八 九 十 总分 累分人 100 签名 题分 20 30 42 8 得分 一、选择题（每题2 分，共20分） 1 2 3 4 5 6 7 8 9 10 得分 评阅人 二、填空题（每空2分，共30分） （1） （2） （3） （4） （5） （6） （7） （8） （9） （10） （11） （12） 得分 评阅人 第 1 页 共3页 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构试卷12—01-9()在线全文阅读。
相关推荐：