数据结构试题B及参考答案(计算机专业)
更新时间:2024-04-28 07:10:01 阅读量: 综合文库 文档下载
- 数据结构试卷及参考答案推荐度:
- 相关推荐
2010-2011 学年第 2 学期 课号 BT11107
课程名称 数据结构 (B卷; 闭卷) 适用班级(或年级、专业) 08011103、104、105
考试时间 120 分钟 班级 学号 姓名 题 号 满 分 得 分 评卷人 一 20 二 20 三 50 四 10 五 六 七 八 九 十 成绩 一、填空题(每小题2分,共20分)
(1) 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的( )和运算等的学科。
(2) 在一个长度为n的顺序表中第i个元素(1 ≤ i ≤ n)之前插入一个元素时,需向后移动( )个元素。
(3)假设以S和X分别表示进栈和退栈操作,则对输入序列a,b,c,d,e进行一系列栈
操作SSXSXSSXXX之后,得到的输出序列为( )。 (4)数据的逻辑结构在计算机存储器内的表示,称为数据的( )。 (5)在具有n个单元的循环队列中,队满时共有____个元素。 (6)二叉树有( )种基本形态。
(7)在具有n个结点的完全二叉树中,若结点i有左孩子,则结点i的左孩子编号为( )。 (8)若用二叉树表示具有n个结点的二叉树,则有( )个空链域。 (9)深度为 k(k>0)的二叉树,至多有( )个结点,第i层上之多有( )结点。 (10) 一个有n个顶点的无向图最多有____条边。
二、选择题(每小题2分,共20分)
1. 研究数据结构就是研究( )。 (A) 数据的逻辑结构
(B) 数据的存储结构
(C) 数据的逻辑结构和存储结构 (D) 数据的逻辑结构、存储结构及其数据的运算 2. 下列算法的时间复杂度是( )
s=0;
for (i=0;i (A)O(m) (B) O(n) (C) O(m×n) (D) O(m+n) 2 2 1 3.计算机识别、存储和加工处理的对象被统称为( ) (A)数据 (B)数据元素 (C)数据结构 (D)数据类型 4. 在一个单链表中,若删除p所指结点的后续结点,则执行____。 (A)p—>next= p—>next—>next; (B) p—>next= p—>next; (C) p= p—>next; p—>next= p—>next—>next; (D) p= p—>next—>next; 5. 在一非空二叉树的中序遍历序列中,根结点的右边____。 (A) 只有右子树上的所有结点 (B) 只有右子树上的部分结点 (C)只有左子树上的部分结点 (D)只有左子树上的所有结点 6.队和栈的主要区别是( ) (A)逻辑结构不同 (B)存储结构不同 (C)所包含的运算个数不同 (D)限定插入和删除的位置不同 7. 设有两个串p和q,求q在p中首次出现的位置的运算称作____。 (A)连接 (B). 模式匹配 (C)求子串 (D) 求串长 8. 具有35个结点的完全二叉树的深度为( )。 (A)5 (B)6 (C)7 (D)8 9.下列编码中属前缀码的是( ) (A){1,01,000,001} (B){1,01,011,010} (C){0,10,110,11} (D){0,1,00,11} 10.用某种排序方法对线性表( 25,84,21,47,15,27,68,35,20)进行排序时,元素序列的变化情况如下: ⑴ 25,84,21,47,15,27,68,35,20 ⑵ 20,15,21,25,47,27,68,35,84 ⑶ 15,20,21,25,35,27,47,68,84 ⑷ 15,20,21,25,27,35,47,68,84 则所采用的排序方法是____。 (A) 选择排序 (B) 希尔排序 (C) 归并排序 (D) 快速排序 2 三、简答题(8小题,共50分) 1.对于如图1所示的树,请问:(5分) (1)树的根结点是哪个结点? (2)结点E的父结点是哪个结点? (3)E的兄弟结点是有哪些结点? (4)树的深度是多少? (5)树的度是多少? 2. 写出图2所示二叉树的先根遍历、中根遍历、后根遍历的结点序列,并将其转换为森林。(8分) D 3. 有一份电文中共使用7个字符:a、b、c、d、e、f、g,它们的出现频率依次为4,5,6,12,8,10,18。要求:(9分) (1)试画出对应的哈夫曼树; (2)每个字符的哈夫曼编码; (3)在对该电文进行最优二进制编码处理后,电文的二进制位数。 图2 I C B A E H ○I ○J ○B ○ A ○C ○D ○E ○F ○G ○图1 F H G 3 4. 分别给出图3所示图的深度优先搜索和广度优先搜索得到的顶点序列。(5分) ③ ① ④ ⑧ ⑨ ⑤ ② ⑥ 0 ⑦ 图3 5. 应用普里姆算法求图4所示带权连通图的最小生成树,要求画出最小生成树的生成过程。(5分) 6.已知一组关键字{49,38,65,97,76,13,27,44,82,35,50},画出由此生成的二叉排序树。(5分) 7.设闭散列表容量为7(散列地址空间0..6),给定表(30,36,47,52,34,40),散列函数H(k)=k mod 6,采用线性探测法解决冲突,di=i,要求:(8分) (1)构造散列表; (2)等概率情况下查找成功时的平均查找长度。 8.写出图5所有可能的拓扑序列。(5分) 图5 4 四、算法填空题(10分) void selectsort (int R[ ] ){ // 按递增序对R[ 0 ]~R[n-1] 进行直接选择排序 int i, j, k, temp ; for (i=0; i<= ⑴ ; i++) { k=i ; for (j= ⑵ ; j<=n-1; j++) if (R[ j ] ⑶ R[ k ] ) k=j; if ( ⑷ temp=R[ i ]; R[ i ] = ⑸ ; R[ k ]=temp; } } }//selectsort { 5 )
正在阅读:
数据结构试题B及参考答案(计算机专业)04-28
高盛2015校园招聘及高盛2015暑期实习生招聘网申过程截图06-01
郑州航院工商管理专业审核评估报告-最新01-24
关于提高海关查验效率的思考09-22
宜兴市公交线路走向及站点设置03-26
意义好的字03-10
哪些人员最易受到室内空气污染的危害06-08
肥城市2012年公开招聘教师简章07-12
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 数据结构
- 试题
- 答案
- 参考
- 计算机
- 专业
- 超市便利店店长工作总结及工作计划
- 第六届浙江省少年文学之星征文比赛三等奖获奖名单
- 益阳市2018年普通初中毕业学业考试样卷-地理(含答案) - 图文
- (精校版)2017年天津文综地理高考试题文档版(含答案) - 图文
- 消防给水及消火栓系统技术规范
- 2012年南昌一中、南昌十中第四次联考 - 图文
- 案例分析题试题库- 仰恩大学精品课程网
- 2014版人教版八年级英语下全册重点及练习(最新)
- 考古学通论知识点
- 员工个人工作总结
- 北安市妇儿办2011年工作总结
- 小型结构物施工方案(1)
- 2014串词最终定稿
- 立案侦查申请书
- 芜湖市劳动合同书(A3打印版)
- 广东省中医药学会音乐治疗专业委员会2010年
- 湘少版五年级下册英语导学案
- 51单片机按键控制花样灯
- Spring技术内幕
- 现代汉语讲义——(邢福义版教材)