试题dsKEYJ050078.doc

山东电子职业技术学院20062007（一）期末考试 数据结构 试题 A 卷 使用班级 J05007、8 共 页题号一二三四五总分分数一、单项选择题 （ 共30分，每题1. 5分 ）（1）数据的基本单位是_。 A、 数据项 B、 数据类型 C、 数据对象 D、 数据元素（2）线性表的链接实现有利于 _ 运算。 A、 插入 B、 读元素 C、 查找 D、 定位（3）若进栈序列为3，5，7，9 不可能的出栈次序为_。 A、 7 5 3 9 B、 9 7 5 3 C、 7 5 9 3 D、 9 5 7 3（4）下面说法正确的是_。 A、 字符串的长度指串中包含的字母个数。B、 字符串的长度指串中包含的不同字符的个数。C、 一个字符串不能说是其自身的一个子串。D、 若串T包含在串S中，则T一定是S的一个子串。（5）广义表(a,b)，(c,d)的表尾是_。 A、 D、 B、 c,D、 C、 （c,d） D、 (c,d)（6）n个顶点的连通图其生成树有_条边。 A、 n -1 B、 n C、 n +1 D、 不一定（7）已知二叉树的先序遍历序列为ABCD，中序遍历序列为BCDA，则后序遍历序列为_。 A、 ABCD B、 BCDA C、 CDBA D、 DCBA（8）有n个结点的二叉链表有_个空链域。 A、 n +1 B、 n C、 n 1 D、 不一定（9）等概率下采用顺序查找算法查找长度为n的线性表，其平均查找长度为_。 A、 n B、 n/2 C、 (n+1)/2 D、 (n1)/2（10）排序的比较次数与序列的初始状态无关的是_。 A、 选择 B、 插入 C、 冒泡 D、 快速（11）下列排序算法中，只有_是稳定的。 A、 希尔 B、 归并 C、 堆 D、 快速（12）对于下列程序段：i=s=0;while (s next = p-next-next B、 p = p-next C、 p =p-next-next D、p-next = p（15）_不能从当前结点出发访问到任何一个结点。 A、单向循环链表B、双向循环链表 C、单向链表D、双向链表（16）设数组datam作为循环队列的存储空间, front为队头指针, rear为队尾指针，则执行入队操作应该使用语句_。 A、rear=rear+1 B、rear=(rear+1)%(m-1) C、rear=(rear-1)%m D、 rear=(rear+1)%m（17）哈希表长m =14，H(key)=key mod 11 ，表中已有4个元素，153861840 1 2 3 4 5 6 7 8 9 10 11 12 13若用二次探测再散列处理冲突，则关键字为49的记录的存储位置是_。 A、 2 B、3 C、8 D、9（18）下列编码中_不是前缀编码。 A、 00,01,10,11 B、 0,1,00,11 C、 0,10,110,111 D、1,01,000,001（19）平衡二叉树上结点的平衡因子不能是 _。 A、2 B、 0 C、 1 D、 -1（20）在哈希表的查找过程中，与给定值进行比较的关键字的个数与_无关。 A、哈希函数 B、处理冲突的方法 C、哈希表的地址 D、哈希表的装填因子二、填空（共20分 ，每空1分）1、数据结构分为逻辑结构和存储结构，链表属于_存储_结构。2、顺序存储的线性表中插入或删除一个元素平均约移动表中_一半_元素。3、设一个A54 按行序优先存储，A00的存储地址是10，每个元素占2个字节，则A32的地址是_38_。4、深度为k的二叉树至多有_2k-1_结点（k1）。5、有n个结点e条边的有向图的邻接表中有_e_个表结点。6、对一棵二叉排序树进行_中序_遍历时，得到的结点序列是一个关键字的有序序列。7、在一个图中，所有顶点的度数之和是边数的_2_倍。8、在有序表（15、21、33、46、58、80、87）中折半查找元素33时，与关键字比较_3_次查找成功。9、想求边稠密的网的最小生成树，采用_普里马_算法更方便，存储结构应该使用_邻接矩阵_。10、有n个顶点的有向完全图有_n(n-1)_条边。11、要想求前面k个大（或小）的元素，使用_堆_排序最方便。若元素已经基本有序， _直接插入_排序效率最高，而最不应该使用_快速_排序。12、队列元素的入队和出队应遵循_先进先出_原则。13、字符串“ABCD”的子串个数是_11_。 14、广义表LS = ( a, (a , b ) , d , e , ( ( i , j ) , k ) ) 的长度是_5_， 深度是_3_。15、对称矩阵可以只保存其下三角，将其n*n个元素压缩存储到长度为_（1+n）*n/2_的一维数组。16、若结点A有3个兄弟，而且B为A的双亲，则B的度为_4_。17、要想对10000个记录进行分块查找，每一块中有_100_个元素效率最高。三、综合应用（共30分）1、写出二叉树叶子结点个数n0与度为2的结点个数n2之间的关系，并证明。（5分）2、写出下图的邻接表，并根据邻接表写出从其顶点V1出发的深度优先遍历序列。（5分）V1V2V3V4V53、将树转换成二叉树，并写出该二叉树的先序遍历序列。（5分）ACBDEGF4、若待排序记录的关键字集合是30 , 4 , 48 , 25 , 95, 13, 90 , 27 , 18 ，采用下列排序算法排成由小到大的序列。（1） 写出快速排序第1趟的排序过程。（5分）（2） 写出2路归并排序的排序过程和排序结果。（5分）（3） 构造一个小顶堆（只画出二叉树形态的最后结果）。（5分）(1) 初始序列 30 , 4 , 48 , 25 , 95, 13, 90 , 27 , 18 i j一次交换 18 , 4 , 48 , 25 , 95, 13, 90 , 27 , 30 i-i j二次交换 18 , 4 , 30 , 25 , 95, 13, 90 , 27 , 48 i j三次交换 18 , 4 , 27 , 25 , 95, 13, 90 , 30 , 48 i-i j四次交换 18 , 4 , 27 , 25 , 30, 13, 90 , 95 , 48 i j-j五次交换 18 , 4 , 27 , 25 , 13, 30, 90 , 95 , 48 ij完成了一趟快速排序。四、算法（从1、2中任选一题，从3、4中任选一题，每题10分，共20分）1、线性表采用链式存储结构，写算法在带头结点的单链表L中，删除所有值为X的结点。2、将带头结点的单链表head就地逆转。3、借助C#中的Stack类，编写C#程序：从键盘输入一个十进制正整数n，输出它的m进制数(m为2-36之间的任意数)。4、借助C#中的Queue类，编写C#程序：从键盘输入一个十进制正整数n，判断它是一个几位数，并将其逆序输出。1、/*线性表采用链式存储结构，本算法实现下列功能：在带头结点的单链表L中，删除所有值为X的结点。算法思想：指针p从首元结点开始，依次向后查找，每找到一个值为X的结点就进行删除，直到p指向链表末尾。*/* 数据结构定义*/typedef int ElemType;typedef struct LNodeElemType data;struct LNode *next; LNode,*LinkList;/* 包含预定义常量和类型的头文件*/#include status.h#include #include /* 删除算法输入：在带头结点的单链表L，欲删除的值X；输出：不包含X的单链表L。*/Status ListDelete_X(LinkList L, ElemType X) LinkList p, prior, tmp; prior =L; /* prior 为p的前驱*/ p=prior - next; while( p != NULL ) if ( p - data = X) /* 删除结点 */ tmp = p ; p = p-next ; prior -next = p; free(tmp); else /* 两个指针同时后移 */ prior = prior - next; p=p-next; return OK;/* end of ListDelete_X*/2、/*线性表采用链式存储结构，本算法实现下列功能：将带头结点的单链表head就地逆转。算法思想：将原链表的头结点和首元结点断开，令其指针域为空，从而构成一个新的空表。然后，将原链表中各结点从首元结点开始，依次插入到这个新表的头部（使每一个刚插入的结点成为新表中的第一个元素结点）。*/* 数据结构定义*/typedef int ElemType;typedef struct LNodeElemType data;struct LNode *next; LNode,*LinkList;/* 包含预定义常量和类型的头文件*/#include status.h#include #include /* 逆转算法输入：在带头结点的单链表head；输出：逆转后的单链表head。*/Status ListReverse (LinkList head) LinkList p, firstNode; p = head - next; /* 保存原链表 */ head - next = NULL ; /* 构成一个新链表 */ while( p != NULL ) firstNode = p ; /* 取出原表的第一个结点 */ p = p - next ; /* 保存剩下的原链表*/ firstNode -next = head -next ; /* 插入到新表头部*/ head -next = firstNode ; return OK;/* end of ListReverse*/3、/ practice5_6a.cs 利用Stack类输出10进制正整数n的m进制using System;using System.Collections;class Change36public static void Main()Stack intStack = new Stack ( ) ;int n,m=1;doConsole.Write(输入正整数n:);n=int.Parse(Console.ReadLine();while(n=0); while (m 36)Console.Write(输入进制数m(2-36):);m=int.Parse(Console.ReadLine();change36(n,m,intStack);string key=;while (intStack.Count 0 )int tmp = (int )intStack.Pop();key+=(char) (tmp = 10 ? 55+tmp : 48+tmp);/end for Console.Write(10进制数0=1进制数2,n,m,key);/end Main()static void change36(int n,int m, Stack intStack)while (n 0 )intStack.Push(n%m);n=n/m;/end while /end change36/end class Change364、using System;using System.Collections;class QueueTest static void Main() Queue intQueue = new Queue (); int n ; do Console .Write (输入