全国2003年1月高等教育自学考试数据结构试题

全国2003年1月高等教育自学考试数据结构试题一、单项选择题(本大题共15小题，每小题2分，共30分。在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内)1.下面程序段的时间复杂度是()。for(i=0;i<n;i++)for(j=1;j<m;j++)A[i][j]=0；A.O(n)B.O(m+n+1)C.O(m+n)D.O(m*n)2.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是()。A.p=p->next;B.p->next=p->next->next;C.p->next=p;D.p=p->next->next;3.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=head,则()。A.p指向头结点B.p指向尾结点C.*p的直接后继是头结点D.*P的直接后继是尾结点4.判定“带头结点的链队列为空”的条件是()。A.Q.front==NULLB.Q.rear==NULLC.Q.front==Q.rearD.Q.front!=Q.rear5.设有两个串T和P，求P在T中首次出现的位置的串运算称作()。A.联接B.求子串C.字符定位D.子串定位6.广义表A=(a,(b),(),(c,d,e))的长度为()。A.4B.5C.6D.77.一棵含18个结点的二叉树的高度至少为()。A.3B.4C.5D.68.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为()。A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA9.无向图中一个顶点的度是指图中()。A.通过该顶点的简单路径数B.与该顶点相邻接的顶点数C.通过该顶点的回路数D.与该顶点连通的顶点数10.已知一个图如下所示，从顶点a出发进行广度优先遍历可能得到的序列为()。A.acefbdB.acbdfeC.acbdefD.acdbfe11.在下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是(B)。A.快速排序B.堆排序C.归并排序D.基数排序12.已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是()。A.{25,36,48,72,23,40,79,82,16,35}B.{25,36,48,72,16,23,40,79,82,35}C.{25,36,48,72,16,23,35,40,79,82}D.{16,23,25,35,36,40,48,72,79,82}13.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为(B)。A.21B.23C.41D.6214.索引非顺序文件的特点是()。A.主文件无序，索引表有序B.主文件有序，索引表无序C.主文件有序，索引表有序D.主文件无序，索引表无序15.倒排文件的主要优点是()。A.便于进行插入和删除运算B.便于进行文件的恢复C.便于进行多关键字查询D.节省存储空间二、填空题(本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分)16.抽象数据类型的特点是将___数据_____和____运算____封装在一起，从而现实信息隐藏。17.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需___前移___一个位置。18.在队列中，允许进行插入操作的一端称为____队尾____，允许进行删除操作的一端称为___队头___。19.如图两个栈共享一个向量空间，top1和top2分别为指向两个栈顶元素的指针，则“栈满”的判定条件是__top1=top2-1____。20.设S1="good",S2="",S3="book"，则S1，S2和S3依次联接后的结果是_goodbook__。21.假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A[9][8][7]的存储地址是__2257_____。22.已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为__（(n-1)/k）*(k-1)+1_或n-(n-1)/k__。23.能够成功完全拓扑排序的图一定是一个__有向无环图__。24.如果在排序前，关键字序列已接近正序或逆序，则在堆排序和快速排序两者之中，选用__堆排序__较为适当。25.假设哈希表的表长为m，哈希函数为H(key)，若用线性探查法解决冲突，则探查地址序列的形式表达为__hi=(H(key)+I)/m___。三、解答题(本大题共4小题，每小题5分，共20分)26.假设通信电文使用的字符集为{a,b,c,d,e,f}，名字符在电文中出现的频度分别为：34，5，12，23，8，18，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子结点的权值小于右孩子结点的权值)，然后分别写出每个字符对应的编码。27.已知一个图如下所示，其顶点按a、b、c、d、e、f顺序存放在邻接表的顶点表中，请画出该图的邻接表，使得按此邻接表进行深度优先遍历时得到的顶点序列为acbefd，进行广度优先遍历时得到的顶点序列为acbdfe。答案：28.已知两个4×5的稀疏矩阵的三元组表分别如下：014160113212218122－22234－2522569342283342544251请画出这两个稀疏矩阵之和的三元组表。解:29.从空树起，依次插入关键字40，8，90，15，62，95，12，23，56，32，构造一棵二叉排序树。(1)画出该二叉排序树(2)画出删去该树中元素值为90的结点之后的二叉排序树。四、算法阅读题(本大题共4小题，每小题5分，共20分)30.如图所示，利用同一循环向量空间实现两个队列，其类型Queue2定义如下：typedefstruct{DataTypedata[MaxSize];intfront[2],length[2];}Queue2;对于i=0或1,front[i]和length[i]分别为第i个队列的头指针和长度域。请在空缺处填入合适的内容，实现第i个循环队列的入队操作。intEnQueue(Queue2*Q,inti,DataTypex){//若第i个队列不满，则元素x入队列，并返回1，否则返回0if(i<0||i>1)return0;if((1))return0;Q->data[(2)]=x;Q->length[(3)]++;return1;}解:(1)(Q->front[i]+Q->length[i]%Maxsize==Q->front[(i+1)%2](2)(Q->front[i]+->length[i]%Maxsize(3)I31.某二叉树的线索链表存储结构如图(b)所示，其中p为指向根结点的指针，图(a)为结点结构。阅读下列算法，并回答问题：(1)写出执行函数调用f(p)的输出结果；(2)简述函数f的功能。voidf(BinThrTreet){while(t){printf(t->data);if(t->lchild)t=t->lchild;elset=t->rchild;}}答案（1）ABDFCEGH(2)先根遍历32.下列函数FindCycle(G,i)的功能是，对一个采用邻接表作存储结构的有向图G，利用深度优先搜索策略寻找一条经过顶点vi的简单回路。数组cycle_path用于保存搜索过程中形成的回路，cycle_path[k]=j(j≥0)表示在回路中顶点vk的下一个顶点是vj。请在空缺处填入合适的内容，使其成为一个完整的算法。vertexfirstedge已知邻接表的顶点表结点结构为：adjvexnext边表结点EdgeNode结构为：intcycle_path[MaxNum];intFindCycle(ALGraph*G,inti){//若回路存在，则返回1，否则返回0intj;for(j=0;j<G->n;j++)cycle_path[j]=-1;returnDFSPath(G,i,i);}intDFSPath(ALGraph*G,intj,inti){EdgeNode*p;intcycled=0;for(p=G->adjlist[j].firstedge;p&&!cycled;p=p->next){cycle_path[j]=p->adjvex;if((1))cycled=1;//已找到回路elseif(cycle_path[p->adjvex]==-1)cycled=(2);}return(3)}(1)(2)(3)32题答案：（1）p->adjvex==i(2)DFSpath(G,p->adjvex,i)(3)cycled33.阅读下列函数algo,并回答问题。(1)假设整型数组A[1..8]中的元素依次为(3，8，9，1，7，4，2，6)。执行函数调用algo(A,8)时，外层while的循环体执行多少次?函数的返回值是多少?(2)简述函数algo(L,n)的功能。intalgo(intL[],intn){inti=0,j,s=1,t=n;while(i!=(n+1)/2){intx=L[s]；i=s;j=t;while(i<j){while(i<j&&L[j]>=x)j--;L[i]=L[j];while(i<j&&L[i]<=x)i++;L[j]=L[i];}L[i]=x;if(i<(n+1)/2)s=i+1;elset=i-1;}if(i==0)return0;elsereturnL[i];}(1)(2)(3)33题答案：（1）外循环执行4次，函数返回值为3。（2）将A[1]至A[8]中不小于A[1]的元素进行递增排序，如调用algo(A,8)时最终排序结果为21346789五、算法设计题(本大题共10分)34.假设以带头结点的单循环链表作非递减有序线性表的存储结构。请设计一个时间复杂度为O(n)的算法，删除表中所有数值相同的多余元素，并释放结点空间。例如：(7，10，10，21，30，42，42，42，51，70)经算法操作后变为(7，10，21，30，42，51，70)34题答案：Exam4(Linklist,L){listnode*p,*q;p=L->next;while(p!=L){q=p->next;while(q&&q->data==p->data){p->next=q->next;free(q);q=p->next;}p->next;}}