数据结构-3

《数据结构》一、选择题（每题3分，共30分）1、在树形结构中，数据元素间存在（）的关系。Ａ、一对一Ｂ、一对多Ｃ、多对多Ｄ、除同属一个集合外别无关系2、下列说法中错误的是（）。Ａ、数据对象是数据的子集Ｂ、数据元素间关系在计算机中的映象即为数据的存储结构Ｃ、非顺序映象的特点是借助指示元素存储地址的指针来表示数据元素间逻辑关系Ｄ、抽象数据类型指一个数学模型及定义在该模型上的一组操作3、下列不属算法特性的是（）。Ａ、有穷性Ｂ、确定性Ｃ、零或多个输入Ｄ、健壮性4、在长为n的顺序表中删除一个数据元素，平均需移动（）个数据元素。Ａ、nＢ、n-1Ｃ、n/2Ｄ、(n-1)/25、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。Ａ、顺序表Ｂ、双链表Ｃ、带头结点的双向循环链表Ｄ、单循环链表6、在一个可存放n个数据元素的顺序栈中，假设以高地址端为栈底，以top为栈顶指针，当向栈中压入一个数据元素时，top的变化是（）。Ａ、不变Ｂ、top=nＣ、top++Ｄ、top--7、设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则删除一个结点的操作是（）。Ａ、rear=front-nextＢ、rear=rear-nextＣ、front=front-nextＤ、front=rear-next8、判定一个栈顶指针为S且不带头结点的链栈为空栈的条件是（）。Ａ、SＢ、S-nextＣ、S-next==NULLＤ、!S9、设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则判定该队中只有一个结点的条件是（）。Ａ、front-nextＢ、rear-nextＣ、front==rearＤ、front!=rear10、串的长度是指（）。A、串中所含不同字母的个数B、串中所含字符的个数C、串中所含不同字符的个数D、串中所含非空格字符的个数二、（10分）设ｎ为正整数，试确定如下程序段中语句“x++;”的频度。for(i=1;i=n;i++)for(j=1;j=i;j++)for(k=1;k=n;k++)x++;三、（15分）设单链表Ｌ如图所示：画出执行如下程序段后，各指针变量及单链表Ｌ的示意图。p=L;for(i=1;i=3;i++){q=(LinkList)malloc(sizeof(LNode));q-data=i*3;q-next=p-next;p-next=q;}四、（10分）设元素的入栈次序为a、b、c、d，且在入栈的过程中允许出栈，试写出所有不可能得到的出栈序列。五、（15分）设a='datastructure'，b='computer'，c='demo'，试求：⑴StrLength(a)的返回值；⑵执行StrInsert(b,4,c)后串b的值；⑶Index(a,'u',10)的返回值；⑷执行Replace(a,'structure',b)后串a的值；⑸执行SubString(s,b,3,3)后串s的值。六、（20分）已知单链表L中含有三类字符的数据元素，即字母字符、数字字符和其他字符，试编写算法将L分割为三个循环链表，其中每个循环链表只含一类字符。答案一、选择题1、B2、B3、D4、D5、A6、D7、C8、D9、C10、B二、设ｎ为正整数，试确定如下程序段中语句“x++;”的频度。for(i=1;i=n;i++)for(j=1;j=i;j++)for(k=1;k=n;k++)x++;答：2)1(2nn三、设单链表Ｌ如图所示：画出执行如下程序段后，各指针变量及单链表Ｌ的示意图。p=L;for(i=1;i=3;i++){q=(LinkList)malloc(sizeof(LNode));q-data=i*3;q-next=p-next;p-next=q;}答：四、设元素的入栈次序为a、b、c、d，且在入栈的过程中允许出栈，试写出所有不可能得到的出栈序列。答：dabcdacbdbacdbcadcabcadbcabdcdabbdacadbc五、设a='datastructure'，b='computer'，c='demo'，试求：⑴StrLength(a)的返回值；⑵执行StrInsert(b,4,c)后串b的值；⑶Index(a,'u',10)的返回值；⑷执行Replace(a,'structure',b)后串a的值；⑸执行SubString(s,b,3,3)后串s的值。答：⑴14⑵'comdemoputer'⑶12⑷'datacomputer'⑸'mpu'六、已知单链表L中含有三类字符的数据元素，即字母字符、数字字符和其他字符，试编写算法将L分割为三个循环链表，其中每个循环链表只含一类字符。答：voidpartition(LinkList&L,LinkList&LC,LinkList&LN,LinkList&LO){//L带头结点，LC为含字母字符的循环链表，LN为含数字字符的循环链表，//LO为含其他字符的循环链表InitCL(LC);InitCL(LN);InitCL(LO);//对三个循环链表进行初始化p=L-next;//p指向第一个结点while(p){q=p;p=p-next;//q指向当前待处理结点，p指向剩余链表if(q-data=’A’&&q-data=’Z’||q-data=’a’&&q-data=’z’){q-next=LC-next;LC-next=q;}//字母字符入循环链表LCelseif(q-data=’0’&&q-data=’9’){q-next=LN-next;LN-next=q;}//数字字符入循环链表LNelse{q-next=LO-next;LO-next=q;}//其他字符入循环链表LO}//whilefree(L);//释放单链表L的头结点}//partitionvoidInitCL(LinkList&L){//对循环链表进行初始化L=(LinkList)malloc(sizeof(LNode));if(!L)exit(OVERFLOW);L-next=L;}一、选择题（每题3分，共30分）1、对稀疏矩阵进行压缩存储的目的是（）。Ａ、便于进行矩阵运算Ｂ、便于输入和输出Ｃ、节省存储空间Ｄ、降低运算的时间复杂度2、设二维数组A5×8按行优先顺序存储，每个数据元素占2个字节，首地址即元素A[0][0]的起始地址为S，则元素A[3][6]的起始地址为（）。Ａ、S+66Ｂ、S+60Ｃ、S+33Ｄ、S+303、设广义表L=((a,()),b,(c,d,e))，则Head(Tail(Tail(L)))的值为（）。Ａ、bＢ、cＣ、(c)Ｄ、(c,d,e)4、下列叙述中错误的是（）。Ａ、对数组一般不做插入和删除操作Ｂ、顺序存储的数组是一个随机存取结构Ｃ、空的广义表没有表头和表尾Ｄ、广义表的表尾可能是原子也可能是子表5、一棵度为3的树中，度为3的结点有2个，度为2的结点有2个，度为1的结点有2个，则度为0的结点有（）。Ａ、5个Ｂ、6个Ｃ、7个Ｄ、8个6、已知二叉树T的先序序列为abdegcfh，中序序列为dbgeachf，则T的后序序列为（）。Ａ、gedhfbcaＢ、dgebhfcaＣ、abcdefghＤ、acbfedhg7、下列叙述中错误的是（）。Ａ、由树的先序遍历序列和后序遍历序列可以惟一确定一棵树Ｂ、二叉树不同于度为2的有序树Ｃ、深度为k的二叉树上最少有k个结点Ｄ、在结点数目相同的二叉树中，最优二叉树的路径长度最短8、设无向图的顶点个数为n，则该图最多有（）条边。Ａ、n-1Ｂ、n(n-1)/2Ｃ、n(n+1)/2Ｄ、n29、设有无向图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)}。对G进行深度优先遍历，正确的遍历序列是（）。Ａ、a,b,e,c,d,fＢ、a,c,f,e,b,dＣ、a,e,b,c,f,dＤ、a,e,d,f,c,b10、设有向图G中有五个顶点，各顶点的度分别为3、2、2、1、2，则G中弧数为（）。Ａ、4条Ｂ、5条Ｃ、6条Ｄ、无法确定二、（10分）设有上三角矩阵(aij)n×n，将其上三角元素逐行存于数组B[m]中（m充分大），使得B[k]=aij，求用i和j表示k的下标变换公式。三、（10分）设二叉树如下，试对其进行先序线索化，画出相应的先序线索二叉树存储结构示意图。四、（15分）设用于通信的电文由8个字母组成，字母在电文中出现的频率分别为0.12、0.31、0.22、0.02、0.03、0.08、0.17、0.05。试为这8个字母设计哈夫曼编码，要求画出设计过程中所构造的哈夫曼二叉树。五、（15分）设有AOE网如下，要求：⑴求图中各顶点代表的事件的最早发生时间和最晚发生时间；⑵求图中各弧代表的活动的最早开始时间和最晚开始时间；⑶列出各条关键路径。六、（20分）设二叉树以二叉链表存储，试设计算法，实现二叉树的层序遍历。答案：一、选择题C、B、D、D、C、B、D、B、D、B二、设有上三角矩阵(aij)n×n，将其上三角元素逐行存于数组B[m]中（m充分大），使得B[k]=aij，求用i和j表示k的下标变换公式。答：jinik2)12(三、设二叉树如下，试对其进行先序线索化，画出相应的先序线索二叉树存储结构示意图。答：四、设用于通信的电文由8个字母组成，字母在电文中出现的频率分别为0.12、0.31、0.22、0.02、0.03、0.08、0.17、0.05。试为这8个字母设计哈夫曼编码，要求画出设计过程中所构造的哈夫曼二叉树。答：编码：0.02:001000.03:001010.05:00110.08:0000.12:1000.17:1010.22:010.31:11五、设有AOE网如下，要求：⑴求图中各顶点代表的事件的最早发生时间和最晚发生时间；⑵求图中各弧代表的活动的最早开始时间和最晚开始时间；⑶列出各条关键路径。答：关键路径１：v1→v2→v5→v7关键路径２：v1→v3→v6→v7六、设二叉树以二叉链表存储，试设计算法，实现二叉树的层序遍历。答：StatusLevelOrderTraverse(BitreeT,Status(*visit)(TElemTypee)){if(!T)returnOK;//空二叉树InitQueue(Q);//初始化辅助队列if(!visit(T-data))returnERROR;//访问根结点EnQueue(Q,T);//指向结点的指针入队while(!QueueEmpty(Q)){//若队列非空DeQueue(Q,p);//队头指针出队if(p-lchild){//先访问p所指结点的左孩子，再访问其右孩子if(!visit(p-lchild-data))returnERROR;EnQueue(Q,p-lchild);}//ifif(p-rchild){if(!visit(p-rchild-data))returnERROR;EnQueue(Q,p-rchild);}//if}//whilereturnOK;}//LevelOrderTraverse一、选择题（每题3分，共30分）1、m阶Ｂ树中的一个分支结点最多含（）个关键字。Ａ、m-1Ｂ、mＣ、m+1Ｄ、[m/2]-1Ｅ、[m/2]Ｆ、[m/2]+12、设有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表，至少要进行（）次探测。Ａ、k-1Ｂ、kＣ、k+1Ｄ、k(k-1)/23、设表中含100个数据元素，用折半查找法进行查找，则所需最大比较次数为（）。Ａ、50Ｂ、25Ｃ、10Ｄ、74、设哈希表地址范围为0~19，哈希函数H(key)=key%17，使用二次探测再散列法处理冲突。若表中已存放有关键字值为6、22、38、55的记录，则再放入关键字值为72的记录时，其存放地址应为（）。Ａ、2