1、数据结构-9 及答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.如果待排序的记录的规模很大，则在下面的排序方式中，我们最好不要选择使用 ( )（分数：2.00）A.快速排序B.直接插入排序C.堆排序D.归并排序2.设数组 A0,m作为循环队列 sq的存储空间，front 为队头指针，rear 为队尾指针，则执行入队操作的语句是( )（分数：2.00）A.sfront=(sfront+1)%mB.sfront=(sfront+1)%(m+1)C.srear=(srear+1)%mD.srear=(srear+1)%(m+1)3.线性表
2、若采用链表存储结构时，要求内存中可用存储单元的地址( )（分数：2.00）A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续不连续都可以4.串是一种特殊的线性表，其特殊性体现在( )（分数：2.00）A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符5.对广义表(a)，(b)进行下面的操作 head(head(a)，(b)后的结果是( )（分数：2.00）A.aB.(C.( )D.不确定6.将含有 83个结点的完全二叉树从根结点开始编号，根为 1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为 41的结点的双亲结点编号为( )（分数：2.0
3、0）A.42B.40C.21D.207.带头结点的单链表 Head为空的判定条件是( )（分数：2.00）A.Head=NULL;B.Head.next=NULL;C.Head.nextHead;D.Head.next=Head8.堆是一个键值序列(k 1，k 2，k，k 1，k 0)，对 i=1，2，n/2，满足( )（分数：2.00）A.kik 2ik 2i+1B.kik 2ik 2i+1C.kik 2i且 kk 2i+1(2i+1D.kik 2i或 kik 2i+l(2i+19.链栈与顺序栈相比，有一个比较明显的优点即( )（分数：2.00）A.插入操作更加方便B.通常不会出现栈满的情况
4、C.不会出现栈空的情况D.删除操作更加方便10.判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用( )（分数：2.00）A.求关键路径的方法B.求最短路径的 Dijkstra方法C.广度优先遍历方法D.深度优先遍历方法11.如果 T2是由有序树 T转换而来的二叉树，那么 T中结点的后序就是 T2中结点的( )（分数：2.00）A.前序B.中序C.后序D.层次序12.假设有一个数组，它的行号从 0到 8，列号从 0到 10，数组中每个元素所占的存储空间为 3个单元，则现在将此数组从某一个地址开始连续存放在一个存储器中，试问至少需要( )个存储单元才能完全将此数组存放进去。（分数：
5、2.00）A.240B.297C.270D.30013.串是任意有限个( )（分数：2.00）A.符号构成的集合B.符号构成的序列C.字符构成的集合D.字符构成的序列14.已知某二叉树的后序遍历序列是 dabec，中序遍历序列是 debac，则它的前序遍历序列是 ( )（分数：2.00）A.a c b e dB.d e c a bC.d e a b cD.c e d b a15.堆排序的最坏时间复杂度为( )（分数：2.00）A.O(B.O(10g2C.O(nlog2D.O(n2)二、B填空题/B(总题数：10，分数：20.00)16.设线性表(a 1，a 2，a 500)元素的值由小到大排列
6、。对一个给定的 k值，用二分法检索查找表中与 k相等的元素，在检索不成功的情况下，至多需比较 1 次。（分数：2.00）填空项 1:_17. 1与数据元素本身的内容和形式无关。（分数：2.00）填空项 1:_18.已知无向图 G的结点数为 n，边数为 e，其邻接表表示中的表结点数与表头结点数之和为 1。（分数：2.00）填空项 1:_19.对带有头结点的链队列 lq，判定队列中具有一个数据元素的条件是 1。（分数：2.00）填空项 1:_20.判断一个没有头结点的单链表 head为空的条件是 1。（分数：2.00）填空项 1:_21.就文件而言，按用户的观点所确定的基本存储单元称为_。按外设的
7、观点所确定的基本存储单元称为_。（分数：2.00）填空项 1:_22.对于一个具有 n条边和 e个顶点的图来说，如果采用邻接表表示，则其空间复杂度为_，若采用邻接矩阵表示，则其空间复杂度为_。（分数：2.00）填空项 1:_23.设有一元多项式 A(x)=7+3x+10x30-4X100+13x101，用单链表给出 A(x)的存储表示为 1。（分数：2.00）填空项 1:_24.在顺序表中，插入或者删除一个元素，需要平均移动_个元素，具体移动的元素个数与_有关。（分数：2.00）填空项 1:_25.一棵树中非叶子结点的个数为 n，与树对应的二叉树中右子树为空的结点的个数为 m，则 m= 1。（
8、分数：2.00）填空项 1:_三、B解答题/B(总题数：4，分数：20.00)26.已知有一关键字序列为(372,81,437,96,205,732,821,634,572,495,264)，如果采用归并排序方法对此序列进行升序排列，请给出每一趟的排序结果。（分数：5.00）_27.假设一棵具有 12个结点的二叉树的存储结构如下图所示，其中 left和 right分别表示此结点左、右孩子的序号，data 表示此结点的数据，根结点为编号为 4的结点。请根据此存储结构画出对应的二叉树，然后回答下面的问题： （分数：5.00）_28.在一棵二叉树中，度为 O的结点个数与度为 2的结点个数和度数之间有
9、什么关系?在一棵完全二叉树中，如果共有 200个结点，则能判断出叶结点的个数吗?如果能，请指出会有多少个叶结点，多少个度为 2的结点?多少个度为 1的结点?如果有 201个结点呢?（分数：5.00）_29.已知有如右图所示的一棵树，请将其转化成二叉树。 （分数：5.00）_四、B算法阅读题/B(总题数：4，分数：20.00)30.以下为单链表按序号查找的运算，分析算法，请在_处填上正确的语句。 pointer find_lklist(1klist head,int i) p=head;j=0; while(_) p=pnext;j+; if(i=j)return(p); else return
10、(NULL); （分数：5.00）填空项 1:_31.以下算法实现若开散列表 HP中存在键值为 K的结点，则将其删除。请分析程序，并在_上填充合适的语句。 void delete_openhash(keytype K,openhash HP) i=H(K); if(HPi=NULL)return; /*空表则退出*/ p=HVi; if(pkey=K)_=pnext;free(p);return;) /*表首结点为待删除结点时的删除*/ while(pnext!=NULL) /*其他情况下的删除*/ q=p;p=pnext; if(pkey=K)_=pnext;delete(p);return
11、;) （分数：5.00）填空项 1:_32.以下运算实现在循环队上的出队列，请在_处用适当的语句予以填充。 int OutCycQueue(CycqueueTp*sq,DataType*x) if(sqfront=_)error(“队空“);return(0);) else_; _; return(1); （分数：5.00）填空项 1:_33.以下为求单链表表长的运算，分析算法，请在_处填上正确的语句。 int length_lklist(lklist head) /*求表的长度。 */ _; j=0; while(pnext!=NULL) _; j+; return(j); /*回传表长*/
12、（分数：5.00）填空项 1:_五、B算法设计题/B(总题数：1，分数：10.00)34.有两个磁盘文件 A、B，各存放一行字母，要求把这两个文件中的信息按字母顺序排列合并，输出到一个新文件 C中。（分数：10.00）_数据结构-9 答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.如果待排序的记录的规模很大，则在下面的排序方式中，我们最好不要选择使用 ( )（分数：2.00）A.快速排序B.直接插入排序 C.堆排序D.归并排序解析：2.设数组 A0,m作为循环队列 sq的存储空间，front 为队头指针，rear 为队尾指针，则执行
13、入队操作的语句是( )（分数：2.00）A.sfront=(sfront+1)%mB.sfront=(sfront+1)%(m+1)C.srear=(srear+1)%mD.srear=(srear+1)%(m+1) 解析：3.线性表若采用链表存储结构时，要求内存中可用存储单元的地址( )（分数：2.00）A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续不连续都可以 解析：4.串是一种特殊的线性表，其特殊性体现在( )（分数：2.00）A.可以顺序存储B.数据元素是一个字符 C.可以链接存储D.数据元素可以是多个字符解析：5.对广义表(a)，(b)进行下面的操作 head(h
14、ead(a)，(b)后的结果是( )（分数：2.00）A.a B.(C.( )D.不确定解析：6.将含有 83个结点的完全二叉树从根结点开始编号，根为 1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为 41的结点的双亲结点编号为( )（分数：2.00）A.42B.40C.21D.20 解析：7.带头结点的单链表 Head为空的判定条件是( )（分数：2.00）A.Head=NULL;B.Head.next=NULL; C.Head.nextHead;D.Head.next=Head解析：8.堆是一个键值序列(k 1，k 2，k，k 1，k 0)，对 i=1，2，n/2，满足( )（分
15、数：2.00）A.kik 2ik 2i+1B.kik 2ik 2i+1C.kik 2i且 kk 2i+1(2i+1 D.kik 2i或 kik 2i+l(2i+1解析：9.链栈与顺序栈相比，有一个比较明显的优点即( )（分数：2.00）A.插入操作更加方便B.通常不会出现栈满的情况 C.不会出现栈空的情况D.删除操作更加方便解析：10.判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用( )（分数：2.00）A.求关键路径的方法B.求最短路径的 Dijkstra方法C.广度优先遍历方法D.深度优先遍历方法 解析：11.如果 T2是由有序树 T转换而来的二叉树，那么 T中结点的后序
16、就是 T2中结点的( )（分数：2.00）A.前序B.中序 C.后序D.层次序解析：12.假设有一个数组，它的行号从 0到 8，列号从 0到 10，数组中每个元素所占的存储空间为 3个单元，则现在将此数组从某一个地址开始连续存放在一个存储器中，试问至少需要( )个存储单元才能完全将此数组存放进去。（分数：2.00）A.240B.297 C.270D.300解析：13.串是任意有限个( )（分数：2.00）A.符号构成的集合B.符号构成的序列C.字符构成的集合D.字符构成的序列 解析：14.已知某二叉树的后序遍历序列是 dabec，中序遍历序列是 debac，则它的前序遍历序列是 ( )（分数：
17、2.00）A.a c b e dB.d e c a bC.d e a b cD.c e d b a 解析：15.堆排序的最坏时间复杂度为( )（分数：2.00）A.O(B.O(10g2C.O(nlog2 D.O(n2)解析：二、B填空题/B(总题数：10，分数：20.00)16.设线性表(a 1，a 2，a 500)元素的值由小到大排列。对一个给定的 k值，用二分法检索查找表中与 k相等的元素，在检索不成功的情况下，至多需比较 1 次。（分数：2.00）填空项 1:_ （正确答案：9）解析：17. 1与数据元素本身的内容和形式无关。（分数：2.00）填空项 1:_ （正确答案：数据的逻辑结构）
18、解析：18.已知无向图 G的结点数为 n，边数为 e，其邻接表表示中的表结点数与表头结点数之和为 1。（分数：2.00）填空项 1:_ （正确答案：n+2e）解析：19.对带有头结点的链队列 lq，判定队列中具有一个数据元素的条件是 1。（分数：2.00）填空项 1:_ （正确答案：lgfrontnext=lqrear）解析：20.判断一个没有头结点的单链表 head为空的条件是 1。（分数：2.00）填空项 1:_ （正确答案：hcad=NULL）解析：21.就文件而言，按用户的观点所确定的基本存储单元称为_。按外设的观点所确定的基本存储单元称为_。（分数：2.00）填空项 1:_ （正确答
19、案：逻辑记录 物理记录）解析：22.对于一个具有 n条边和 e个顶点的图来说，如果采用邻接表表示，则其空间复杂度为_，若采用邻接矩阵表示，则其空间复杂度为_。（分数：2.00）填空项 1:_ （正确答案：O(n+c) O(n 2)）解析：23.设有一元多项式 A(x)=7+3x+10x30-4X100+13x101，用单链表给出 A(x)的存储表示为 1。（分数：2.00）填空项 1:_ （正确答案：*）解析：24.在顺序表中，插入或者删除一个元素，需要平均移动_个元素，具体移动的元素个数与_有关。（分数：2.00）填空项 1:_ （正确答案：约表长的一半 该元素在线性表中的位置）解析：25.
20、一棵树中非叶子结点的个数为 n，与树对应的二叉树中右子树为空的结点的个数为 m，则 m= 1。（分数：2.00）填空项 1:_ （正确答案：n+1）解析：三、B解答题/B(总题数：4，分数：20.00)26.已知有一关键字序列为(372,81,437,96,205,732,821,634,572,495,264)，如果采用归并排序方法对此序列进行升序排列，请给出每一趟的排序结果。（分数：5.00）_正确答案：()解析：归并排序的基本思想是：第 l趟归并排序是，将待排序的文件 R1n看作是 n个长度为 1的有序子文件，将这些文件两两归并，若 n是偶数，则得到 n/2个长度为 2的有序文件，若 n
21、为奇数，则最后一个文件轮空，此时得到n/2-1 个有序文件长度为 2，最后一个文件长度为 1，第 2越是将第 1趟得到的各个有序子文件进行两两归并。这样依次类推，直到得到一个长度是 n的有序文件为止。按照上述规则，我们得到各趟归并的结果如下： 初始：372,81,437,96,205,732,21,634,572,495,264 第 1趟归并后：81,37296,437205,732634,821495,572264 第 2趟归并后：81,96,372,437205,634,732,821264,495,572 第 3趟归并后：81,96,205,372,437,634,732,821264,
22、495,572 第 4趟归并后：81,96,205,264,372,437,495,572,634,732,82127.假设一棵具有 12个结点的二叉树的存储结构如下图所示，其中 left和 right分别表示此结点左、右孩子的序号，data 表示此结点的数据，根结点为编号为 4的结点。请根据此存储结构画出对应的二叉树，然后回答下面的问题： （分数：5.00）_正确答案：()解析：在二叉树的链表中，每个结点不仅存放了结点的数值，还存放着指向其左、右孩子的指针，则按照此题中给出的条件，编号为 4的结点为根结点，即 A为根结点，然后，再根据 A的左、右孩子指针所指向的编号，分别找出 A的左、右孩子
23、为 B，E，然后根据左、右孩子的左右孩子指针域所指向的编号，分别找出左、右孩子的左、右孩子，直到所找到的结点的左、右孩子的指针域都为 0时，则按照以上规则我们得到此二叉树的结构为： 28.在一棵二叉树中，度为 O的结点个数与度为 2的结点个数和度数之间有什么关系?在一棵完全二叉树中，如果共有 200个结点，则能判断出叶结点的个数吗?如果能，请指出会有多少个叶结点，多少个度为 2的结点?多少个度为 1的结点?如果有 201个结点呢?（分数：5.00）_正确答案：()解析：在一棵二叉树中，度数为 0的结点(叶结点)的个数总是比度为 2的结点的个数多 1。根据完全二叉树的定义：若一棵二叉树至多只有最
24、下面的两层上结点的度数可以小于 2，并且最下一层上的结点都集中在该层最左边的若干住置上，则我们可以得出这样一个结论：在一棵完全二叉树上，或者没有度为 1的结点。则根据以上分析，我们可以这样计算此题：设度数为 2的结点有 n个，则必有 n+1个度为 0的结点，即度数为 2和度数为 0的结点数之和为 2n+1(是奇数)，于是得出，如果一棵完全二叉树的结点总数为奇数，则此树中必然不存在度为 1的结点，若完全二叉树中结点总数为偶数，则必然有 1个度为 1的结点存在，于是若完全二叉树中有 200个结点，就必有 100个对结点，99 个度数为 2的结点，12 个度数为 1的结点，如果二叉树中有 201个结
25、点，则必有 101个叶结点，100 个度数为 2的结点，没有度数为 1的结点。29.已知有如右图所示的一棵树，请将其转化成二叉树。 （分数：5.00）_正确答案：()解析：将一棵树转换成二叉树的规则如下： (1)在所有的兄弟结点之间加一条线； (2)对于每个结点，除了保留与长子的连线外，去掉该结点和其他孩子的连线，则根据以上两个规则，我们得到转换后的二叉树为(从此图我们可以得到，将一棵普通树转换成二叉树后，其对应的二叉树的右子树为空)： 四、B算法阅读题/B(总题数：4，分数：20.00)30.以下为单链表按序号查找的运算，分析算法，请在_处填上正确的语句。 pointer find_lkli
26、st(1klist head,int i) p=head;j=0; while(_) p=pnext;j+; if(i=j)return(p); else return(NULL); （分数：5.00）填空项 1:_ （正确答案：(pnext!=NULL) if(HPi=NULL)return; /*空表则退出*/ p=HVi; if(pkey=K)_=pnext;free(p);return;) /*表首结点为待删除结点时的删除*/ while(pnext!=NULL) /*其他情况下的删除*/ q=p;p=pnext; if(pkey=K)_=pnext;delete(p);return;
27、) （分数：5.00）填空项 1:_ （正确答案：HPi qnext）解析：32.以下运算实现在循环队上的出队列，请在_处用适当的语句予以填充。 int OutCycQueue(CycqueueTp*sq,DataType*x) if(sqfront=_)error(“队空“);return(0);) else_; _; return(1); （分数：5.00）填空项 1:_ （正确答案：sqrear sqfront=(sqfront+1)%maxsize *x=sqdatasqfront）解析：33.以下为求单链表表长的运算，分析算法，请在_处填上正确的语句。 int length_lkli
28、st(lklist head) /*求表的长度。 */ _; j=0; while(pnext!=NULL) _; j+; return(j); /*回传表长*/（分数：5.00）填空项 1:_ （正确答案：p=head p=pnext）解析：五、B算法设计题/B(总题数：1，分数：10.00)34.有两个磁盘文件 A、B，各存放一行字母，要求把这两个文件中的信息按字母顺序排列合并，输出到一个新文件 C中。（分数：10.00）_正确答案：()解析：可先分别将 A、B 文件的内容读出放到数组 C中，再对数组 C排序，最后再将数组内容写到文件 C中，程序为： #includestdio.h mai
29、n() /*合并 A、B 文件内容到 C文件中*/ FILE*fp; int i,j,n,m; char c160,t,ch; if(fp=fopen(“A“,“r“)=Null) printf(“文件 A cant open/n“); exit(0); else printf(“/n文件 A的内容为/n“) for(i=0;(ch=fgetc(fp)!=EOF:i+) Ci=oh; putchar(C-i); fclose(fp); m=i; if(fp=fopen(“B“,“r“)=Null) printf(“B文件 cant open/n“); exit(0); else printf(“/nB文件内容是/n“); for(i=m;(ch=fgetc(fp)!=EOF;i+) Ci=ch; putchar(i); fclose(fp); n=i;/*排序*/ for(i=0;in;i+) for(j=i+1;jm,j+) if(Cicj) t=ci; ci=cj; cj=t; printf(“/nC 文件是/n“); fp=fopen(“c“,“w“) /* 写入 C文件中*/ for(i=0;im;i+) putchar(ci,fp); putchar(ci); fclose(fp); /*main*/
