数据结构

1考试科目:《数据结构》第一章至第四章（总分100分）时间：90分钟______________学习中心（教学点）批次：层次：专业：学号：身份证号：姓名：得分：一、选择题（每题3分，共30分）1、（）是数据的不可分割的最小单位。Ａ、数据元素Ｂ、数据对象Ｃ、数据项Ｄ、数据结构2、若采用顺序映象，则数据元素在内存中占用的存储空间（）。Ａ、一定连续Ｂ、一定不连续Ｃ、可连续可不连续3、下列说法中错误的是（）。Ａ、栈是一种非线性结构Ｂ、一个数据元素由一或多个数据项构成Ｃ、在顺序存储结构中，结点间的逻辑关系由存储单元的邻接关系来体现Ｄ、语句的频度就是语句的执行次数4、以下属单链表优点的是（）。Ａ、顺序存取Ｂ、插入操作能在O(1)的时间复杂度上完成Ｃ、插入时不需移动数据元素Ｄ、节省存储空间5、顺序表中数据元素的存取方式为（）。Ａ、随机存取Ｂ、顺序存取Ｃ、索引存取Ｄ、连续存取6、设输入序列为ABC，输出序列为CBA，则经过的栈操作为（）。Ａ、push,pop,push,pop,push,popＢ、push,push,push,pop,pop,popＣ、push,push,pop,pop,push,popＤ、push,pop,push,push,pop,pop7、若用一个大小为6的数组来实现循环队列，且当前队尾指针rear和队头指针front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。Ａ、1和5Ｂ、2和4Ｃ、4和2Ｄ、5和18、串是一种特殊的线性表，其特殊性体现在（）。Ａ、可以顺序存储Ｂ、数据元素是一个字符Ｃ、可以链接存储Ｄ、数据元素可以是多个字符9、设串s='abcdefgh'，则其子串数为（）。Ａ、8Ｂ、37Ｃ、36Ｄ、9210、设串s1='abcdefg'，s2='ab'，则Concat(s1,s2)的返回值（）。Ａ、abＢ、cdefgＣ、abcdefgＤ、abcdefgab二、（10分）设n为正整数，则在下面的程序段中，语句“a+=2;”的频度为多少？for(x=0;xn;++x)for(y=0;yn;++y)a+=2;三、（15分）设单链表L带头结点且非空，指针变量p指向L中的一个结点，且该结点既不是L中的第一个结点，也不是L中的最后一个结点，指针变量s指向一个待插入L的新结点。试写出能完成下列操作的语句序列。⑴在p所指结点之前插入s所指结点；⑵在L中最后一个结点之后插入s所指结点；⑶删除p所指结点的直接后继；⑷删除L中第一个结点。四、（10分）有5个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？五、（15分）设a='colomn'，b='Howareyou!'，c='please'，试求：⑴StrLength(b)的返回值；⑵Index(a,'o',5)的返回值；⑶执行StrInsert(a,3,c)后串a的值；⑷执行Replace(c,'e','x')后串c的值；⑸执行SubString(s,b,5,3)后串s的值。六、（20分）假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数，试写出其入队和出队算法（在出队算法中要返回队头元素）。答案：一、选择题（每题3分，共30分）3C、A、A、C、A、B、B、B、B、D二、设n为正整数，则在下面的程序段中，语句“a+=2;”的频度为多少？for(x=0;xn;++x)for(y=0;yn;++y)a+=2;答：n2三、设单链表L带头结点且非空，指针变量p指向L中的一个结点，且该结点既不是L中的第一个结点，也不是L中的最后一个结点，指针变量s指向一个待插入L的新结点。试写出能完成下列操作的语句序列。⑴在p所指结点之前插入s所指结点；⑵在L中最后一个结点之后插入s所指结点；⑶删除p所指结点的直接后继；⑷删除L中第一个结点。答：⑴q=L;while(q-next!=p)q=q-next;//q指向p的直接前驱s-next=p;q-next=s;⑵q=L;while(q-next)q=q-next;s-next=NULL;q-next=s;⑶q=p-next;//q指向待删结点p-next=q-next;free(q);⑷q=L-next;L-next=q-next;free(q);四、有5个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最4先出栈（即C第一个且D第二个出栈）的次序有哪几个？答：CDEBACDBEACDBAE五、设a='colomn'，b='Howareyou!'，c='please'，试求：⑴StrLength(b)的返回值；⑵Index(a,'o',5)的返回值；⑶执行StrInsert(a,3,c)后串a的值；⑷执行Replace(c,'e','x')后串c的值；⑸执行SubString(s,b,5,3)后串s的值。答：（1）12（2）0（3）’copleaselomn’（4）’plxasx’（5）’are’六、假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数，试写出其入队和出队算法（在出队算法中要返回队头元素）。答：#defineMAXQSIZE100typedefstruct{ElemTypebase[MAXQSIZE];intrear;intlength;}Queue;StatusEnQueue(Queue&Q,ElemTypee){if(Q.length==MAXQSIZE)returnERROR;Q.rear=(Q.rear+1)%MAXQSIZE;Q.base[Q.rear]=e;Q.length++;returnOK;}//EnQueue5StatusDeQueue(Queue&Q,ElemType&e){if(!Q.length)returnERROR;front=(Q.rear-Q.length+1)%MAXQSIZE;e=Q.base[head];Q.length--;}//DeQueue考试科目:《数据结构》第五章至第七章（总分100分）时间：90分钟______________学习中心（教学点）批次：层次：专业：学号：身份证号：姓名：得分：一、选择题（每题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、下列叙述中错误的是（）。6Ａ、由树的先序遍历序列和后序遍历序列可以惟一确定一棵树Ｂ、二叉树不同于度为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网如下，要求：⑴求图中各顶点代表的事件的最早发生时间和最晚发生时间；⑵求图中各弧代表的活动的最早开始时间和最晚开始时间；⑶列出各条关键路径。7六、（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四、设用于通信的电文由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:10190.22:010.31:11五、设有AOE网如下，要求：⑴求图中各顶点代表的事件的最早发生时间和最晚发生时间；⑵求图中各弧代表的活动的最早开始时间和最晚开始时间；⑶列出各条关键路径。答：关键路径１：v1→v2→v5→v7关键路径２：v1→v3→v6→v7六、设二叉树以二叉链表存储，试设计算法，实现二叉树的层序遍历。答：StatusLevelOrderTraverse(BitreeT,Status(*visit)(TElemTypee)){if(!T)returnOK;//空二叉树InitQueue(Q);//初始化辅助队列10if(!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考试科目:《数据结构》第五章至第七章（总分100分）时间：90分钟______________学习中心（教学点）批次：层次：专业：学号：身份证号：姓名：得分：一、选择题（每题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