南理工初试试题
南理工初试试题,很完整的试题哦南京理工大学课程考试试卷 (学生考试用) 课程名称: 数据结构 学分: 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;
- 1
- 粉丝: 0
- 资源: 1
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 2024年全国计算机二级笔试题题目带答案一共46道题目.doc
- 【零基础学Python】项目实战:使用Django框架搭建私人博客第(二)天 - 注册、登录功能实现
- 计算机科学与技术学院编译原理实验报告文档.doc
- 上传即可使用的在线叫号系统源码
- 放大器的种类及其主要特性参数
- llvm-toolchain-8.0.1-7-amd64-linux-gnu-debian-10.tar.gz
- exe程序msys2安装包windows版本msys2-x86-64-20230127.exe
- llvm-toolchain-18.1.6-1-amd64-linux-gnu-debian-10.tar.gz
- UL 61800-5-1-2022 行业标准
- 放大器的种类及其主要特性参数