南理工初试试题

南理工初试试题，很完整的试题哦南京理工大学课程考试试卷 （学生考试用） 课程名称： 数据结构 学分： 3 大纲编号 062204 试卷编号： 考试方式： 闭卷 满分分值： 100 考试时间： 120 分钟 组卷日期： 2006年5月18日 组卷教师（签字） 张宏 审定人（签字） 王树梅 学生班级： 计算机学院 04级 学生学号： 学生姓名： 一、 选择题（1.5*20=30分） 1.若以{4，5，6，3，8}作为叶子结点的权值构造哈夫曼树，则带权路径长度是 A) 55 B)68 C)59 D)28 2. 无向图G=（V，E），其中：V={ a,b,c,d,e,f} , E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},对该图进行广度优先遍历，得到的顶点序列正确的是 A) a,b,e,c,d,f B) a,c,f,e,b,d C) a,e,b,c,f,d D) a,e,d,f,c,b 3. 对关键字码集合K={53，30，37，12，45，24，96}，从空二叉树出发建立与集合K对应的二叉排序树，若希望得到树的高度最小，应选择下列哪个输入序列 。 A)45，24，53，12，37，96，30 B)12，24，30，37，45，53，96 C)37，24，12，30，53，45，96 D)30，24，12，37，45，96，53 4. 已知一组数{20，8，6，2，30，1}的排序过程为： （1）20，8，6，2，30，1 （2）1，8，6，2，30，20 （3）1，2，6，8，30，20 （4）1，2，6，8，20，30 问它是下面那一种排序： A)快速排序 B) 直接插入排序 C) 起泡排序 D) 选择排序 5．计算机算法必须具备输入、输出和 等五个特征。 A) 可行性、可移植性和可扩充性 B)可行性、确定性和有穷性 C) 确定性、有穷性和稳定性 D)易读性、稳定性和安全性 6．设哈希表长为14，哈希函数是H(key)=key,表中已有数据的关键字为15,38,61,84共四个，现要将关键字为26的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是 A) 8 B) 3 C)2 D)9 7．在一个单链表中，若要删除p所指结点的后继结点，则执行 。 A) p=p->next; p->next=p->next->next B) free(p->next) (C语言格式) 或 delete p->next (C++语言格式) C) p=p->next->next; D) p->next=p->next->next 8. 数组A的每个元素需要4个字节存放，数组有8行 10列，若数组以行为主顺序存放在内存SA开始的存储区中，则A中8行5列的元素的位置是 A) SA+74 B)SA+292 C)SA+296 D)SA+300 9-10．在一棵7阶B树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有 (1) 个关键字；若在某结点中删去一个关键字而导致结点合并，则该结点中原有的关键字的个数是 (2) 。 (1) A)6 B)5 C)4 D)3 (2) A)4 B)3 C)2 D)1 11．已知四个元素a,b,c,d依次进栈，进栈过程中可出栈，下面那一种出栈顺序是不正确的 A)a,d,c,b B)b,c,d,a C)c,a,d,b D)c,d,b,a 12．队列操作的原则是 。 A) 先进先出 B) 后进先出 C) 只能进行插入 D)只能进行删除 13．在有n 个结点的二叉链表中,值为空链域的个数为 A)n-1 B)2n-1 C)n+1 D)2n+1 14．具有1080个结点的完全二叉树的深度为 A) 12 B)10 C)11 D)13 15．若已知一个栈的入栈序列是元素1，2，3，....，n，其输出序列为p1,p2,p3,…pn,若p1是n，则pi是( ) A) i B)n-i C)n-i+1 D)不确定 16．对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是 A) n B)(n-1)2 C)n-1 D)n2 17．对线性表进行二分查找时，要求线性表必须 A)以顺序方式存储 B)以链接方式存储 C)以顺序方式存储，且数据有序 D)以链接方式存储，且数据有序 18．若用起泡排序对序列{14,26,29,41,52,5}从小到大排序,需要 次比较 A)15 B) 28 C)3 D)21 19．有一个有序表为{1，3，9，12，32，41，45，62，70，77，82，95，100}，当二分查找值62的数据时要 次比较成功。 A)1 B) 2 C) 4 D) 3 20．设双向循环链表中结点的结构为（data,pre,next）。若在指针p所指结点之后插入结点s，则应执行下列 操作 A)p->next=s; s->pre=p; p->next->pre=s; s->next=p->next; B)p->next=s; p->next->pre=s; s->pre=p; s->next=p->next; C)s->pre=p; s->next=p->next; p->next=s; p->next->pre=s; D)s->pre=p; s->next =p->next; p->next->pre=s; p->next=s; 二、填空题（19分,其余每空1分） 1．已知h是无表头结点的单链表，且p结点既不是首元结点，亦不是尾元结点，试从下列提供答案中选择合适的语句序列(给出序号)： a.在p结点后插入s结点的语句序列是 (1) ； b. 在p结点前插入s结点的语句序列是 (2) ； c.在表首插入s结点的语句序列是 (3) ； d. 在表尾插入s结点的语句序列是 (4) ； (1) p->next=s; (2) p->next=p->next->next; (3) p->next=s->next; (4) h=s; (5) p=h; (6) s->next=NULL; (7) q=p; (8) while(p->next!=NULL)p=p->next; (9) while(p->next!=q )p=p->next; (10) p=q; (11) p=h; s->next=h; (12) h=p; (13) s->next=p->next; 2．图的遍历分为 (5) 和 (6) 。 3．假设一棵二叉树的中序序列为DCBGEAHFIJK和后序序列为DCEGBFHKJIA，则先序序列为： (7) 。 4．深度为k的完全二叉树至少有 (8) 个结点；至多有 (9) 结点。 5．在一棵二叉树中，度为1的结点有40个，总的结点数为99，则二叉树中叶子结点数共有 (10) 。 6．在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂时，则左边结点有 (11)　 个关键字；右边结点的关键字数是 (12)　 。 7.求图的最小生成树有两种算法， (13) 算法适合于求稀疏图的最小生成树。 8．一个深度为k的，具有最少结点数的完全二叉树按层次，(同层次从左向右)用自然数依此对结点编号，则编号最小的叶子的序号是 (14) ；编号是i的结点所在的层次号是 (15) （根所在的层次号规定为1层）。 三、简答题（35分） 1． 已知有向图的带权矩阵为： 1)（3分）画出该有向图。 2) (3分) 按Dijkstra算法,给出从顶点1(顶点标号从1计)到其余顶点的最短路径长度以及经过的中间点。 3）（3分）画出该图邻接表存储结构示意图。 4）（3分）画出对应无向图的最小生成树，给出生成树边权之和。(如果去掉方向后,一对顶点之间有两条以上的边,只保留权值最小的边) 2．已知关键字的集合{56，8，15，80，10，22，28，50，60,40,90} （1）（3分）试按给出的序列构造一棵平衡二叉树。 （2）（3分）试构造3阶B_树。 （3）（3分）写出依次删除关键字60,40后的B_树。 （4）（3分）按以上数据, 用链地址法处理冲突(Hash函数H（key）=key % 13)，画出示意图(不要写算法) 3．（3分）已知三棵树的森林如下，试把它转化为二叉树 A G N / \ / | \ / \ B C H I K O P / | \ / \ / | \ D E F L M R S T 4．（4分）按大顶堆将序列{56，8，15，80，10，22，28，50，60,40,90}调整为堆，写出最后的数据序列 5．（4分）给出拓扑排序算法描述（不用写C/C++算法） 四、算法设计（用类-C/类-C++描述）（16分） 1．(8分)完成一个二叉树左右子树交换的递归算法。 2．(8分)设在一个带头结点的双向链表中，所有结点的数据元素按值递增顺序排列，写一算法，删除表中所有大于min，小于max的元素（若存在）。双链表的定义如下： typedef struct DLnode{ int data; DLnode *pre, *next; }DLnode;