1252数据结构历年试题及答案

《1252数据结构历年试题及答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、试卷代号:1252屮央广播电视人学2012-2013学年度第二学期“开放木科”期末考试数据结构【本）试题一、单项选择题（每小题2分，共30分）1.在C语言屮，顺序存储长度为3的字符串，需耍占用（）个字节。A.4B.3C.6D.122o串函数StrCat（a,b）的功能是进行串（）。A.比较B.复制Co赋值D.连接3.-棵冇n个结点采用链式存储的二叉树中，共冇（）个指针域为空。A.n+1B・nC.n~lD.n-24.设一棵哈夫曼树共有n个非叶结点，则该树有（）个叶结点。A.nB.n+1C.n-1D.2n5.从一个栈顶指针为top的链栈屮删除一个结点

2、时，用变量x保存被删结点的值，贝IJ执行（）。A.x=top->data;top=top->nextB.x=top->dataC.top=top->next;x=top->dataD.top=top->next;x=data6.-•棵完全二义树共有5层，且笫5层上有六个结点，该树共有（）个结点。A.30B.20C.21D.233.在一个无向图中，所冇顶点的度数Z和等于边数的（）倍。±；.Z.3C.1.5D.24.己知如图1所示的一个图，若从顶点V,出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。A.V1V2V4V8V5V3V6

3、V7B.VIV2V4V5V8V3V6V7C.VjVaV^VgVaVsVsV,的一种顶点序列为（）。A.abcedfB.abcefdC.aebcfd10.对二义排序树进行（）遍历，可以使遍历所得到的序列是有序序列。A.按层次B.后序C.屮序D.前序11.在有序表（2,4,7,14,34,43,47,64,75,80,90,97,120）中，用折半查找法查找值80时，经（）次比较后查找成功。A.4B.2•皆a月肌C・3D.510.有一个长度为9的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。A.25/10B.25/9C

4、.20/9D.17/910.排序算法中，从未排序序列中依次取出元索与已排序序殂（初始为空）中的元索进行比较（要求比较次数尽量少），然示将其放入已排序序列的正确位置的方法是（）。A.冒泡B.玄接插入C.折半插入D.选择排序11.一组记录的关键字序列为（46,79,56,38,40,84）,利用快速排序，以第一个关键字为分割元索，经过一次划分后结果为（）oA.40,38946,79956,84B.40,38946,56,79,84C.40,3&46,84,56,79D.38,40,46956,79,8412.排序方法屮，从尚未排序序列屮挑选元索，并将

5、具依次放人己排序序列（初始为空）的—•端的方法，称为（）排序。A.归并B.插入C.快速D.选择二、填空题（毎小题2分。共24分）13.在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是——、、右指针。14.-棵二叉树屮顺序编号为i的结点，若它存在左、右孩了，则左、右孩了编号分别为•_••―、•…~01&串的两种最基本的存储方式是一和——一。19.-棵有2n-l个结点的二叉树，其每一个非叶结点的度数都为2,则该树共有——个叶结点。20.对于一棵具有n个结点的二叉树，其相应的链式存储结构屮共有一一个指针域为空。21.遍历二叉排序树可得到一个有

6、序序列。19.如图3所示的二叉树，其后序遍历序列为2%图320.如图4所示的二叉树，其先序遍历序列为妒图421.图的深度优先搜索和广度优先搜索序列不一定是唯一•的。此断言是一的。（回答正确或不正确）22.二叉树为二叉排序的充分必要条件是其任一结点的值均人于其左孩子的值、小于其右孩了的值。这种说法是的。（回答正确或不正确）23.对记录序列排序是指按记录的某个关键字排序，记录序列按—排序结果是唯一的。24.按某关键字对记录序列排序，若在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。三、综合题(每小题10分。共30分)19.设

7、查找表为(16,15,20,53,64,7),⑴川冒泡法对该表进行排序(要求升序排列)，写出每一趟的排序过程，通常'对n个元索进行冒泡排序要进行多少趟冒泡?第J趟要进行多少次元素间的比较？(2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树。(婆求以数据元素作为树结点)。20.(1)设有查找表{5,14,2,6,18,7,4,16,3),依次取表屮数据，构造一棵二叉排序树。(2)说明如何由序列的二义排序树得到相应序列的排序结果。21.(1)对给定权值2,1,3,3,4,5,构造哈夫曼树(要求每个结点的左子树根结点的权小于等于右子树根

8、结点的权)。(2)给出各权值的哈夫曼编码。四、程序填空题【每空2分。共16分)22.设线性表为(6,10,16,4),以下程序用说明结构