数据结构安徽大学考试

安徽大学数据结构一、填空题1、算法的5个重要特性是_____有穷性_____、___确定性________、___可行性_____、输入和输出。2、单链表中，除首元素结点外，其它任一元素结点的存储位置由__其前驱的指针域_________指示。3、在双向链表中，欲在p所指结点之前插入一个由s指向的结点，请完成有关操作。s-prior=p-prior;p-prior=s;p-next=s-next；s-next=p;4、对于栈只能在____栈顶____插入和删除元素；对于队列只能在___队尾______插入元素和__队头_____删除元素。5、在模式匹配的KMP算法中用到了一个next函数，若next[j]=k，则说明在模式串T中存在一个与“T1T2...Tk-1”相等的子串“__Tj-k+1….Tj-1_______________”。6、假设有二维数组A68，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A共占用_____288_______个字节的存储单元，按行存储时，元素A25的第一个字节的地址为______1126_______。8、若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度为__69____。9、广义表g=(())的表头是_____()_____，表尾是____()______。二、单项选择题1、线性结构的顺序存储结构是一种___A___的存储结构，线性结构的链式存储是一种____B_的存储结构。A.随机存取B.顺序存取C.索引存取D.散列存取2、执行下面程序段时，S语句的执行次数为__A_______。for(inti=1;i=n-1;i++)for(intj=i+1;j=n;j++)S;A.(1)/2nnB.2/2nC.(1)/2nnD.n3、将两个各有N个元素的有序表归并为一个有序表，其最少的比较次数是__A______。A.N;B.2N-1;C.2N;D.N-14、已知4个元素进栈的顺序依次为A,B,C,D，则下面哪一个出栈序列是不可能得到的__C___。A.ABCD;B.CBAD;C.CADB;D.BCAD5、G是一个非连通无向图，共有28条边，则该图至少有____B___个顶点。A.8B.9C.10D.126、某二叉树的层序序列是abcdefgh，中序序列是dbgehacf，则该树的后序序列是_______C_________。A.fahgbecB.eagbfdcC.dghebfcaD.acdbfge三、应用题1．对图2所示的二叉树，要求图2（1）将其转换为树或森林，画出转换后的结果。（2）给出对该树或森林分别进行先根遍历和后根遍历得到的结点序列。（1）AEGBCDFHI(2)先根ABCDEFGHI后根BCDAFEHIGFHGEAICDB四、算法阅读题1、阅读下面算法，按要求作答，其中Push(S,d)表示将数据元素d压入栈S中，Pop(T,d)表示T的栈顶元素出栈并存入d中。intalgo(StackS,inte){intd;StackT;InitStack(T);while(!StackEmpty(S)){Pop(S,d);if(d!=e)Push(T,d);}//whilewhile(!StackEmpty(T)){Pop(T,d);Push(S,d);}}（1）假设栈S中的原始数据从栈底至栈顶依次为：3，5，7，12，5，6，8；e的值为5。请写出算法执行完后栈S中从栈底至栈顶的数据元素序列。371268（2）简述该算法的功能。将栈S中所有等于e的元素利用栈T从S中删除2、已知数组a中存放着两组数据元素序列（a0，a1，．．．，am-1，b0，b1，．．．，bn-1）。下面算法利用原存储空间将a中的数据元素序列就地互换为（b0，b1，．．．，bn-1，a0，a1，．．．，am-1），算法思想可以描述为：（1）把数组a中的数据元素序列（a0，a1，．．．，am-1，b0，b1，．．．，bn-1）就地逆置为（bn-1，．．．，b1，b0，am-1，．．．，a1，a0）。（2）把数组a中的数据元素序列（bn-1，．．．，b1，b0，am-1，．．．，a1，a0）就地逆置为（b0，b1，．．．，bn-1，am-1，．．．，a1，a0）。(3)把数组a中的数据元素序列（b0，b1，．．．，bn-1，am-1，．．．，a1，a0）就地逆置为（b0，b1，...，bn-1，a0，a1...，am-1）。根据上述算法思想，请在空缺处填上适当的语句，以完善算法功能。voidconverse(ElemTypea[],intlow,inthigh){//将数组a中自下标low至high的一段数据元素逆置intn,i;ElemTypex;n=(high-low+1)/2;//n为循环次数for(i=0;in;i++){x=a[low+i];__a[low+i]=a[high-i]______;__a[high-i]=x__________;}}voidexchange(ElemTypea[],intm,intn){converse(a,0,m+n-1);//将数组a中的m+n个元素就地逆置_converse(a,0,n-1)_____________________________;_converse(a,n,m+n-1)_____________________________;}五、算法设计下面两题的数据类型定义和函数首部均已给出，请按要求完成算法设计。１．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子结点的个数。typedefstructTnode{TelemTypedata;//结点数据域structTnode*firstchild*nextsibling;//指向长子和右兄弟的指针}CSnode,*CStree;voidleafcount(CStreeT,int*count){//统计以孩子—兄弟链表存储表示的树T的叶子结点数目，结果存于count所指单元，//T为指向根结点的指针if(!T-firstchild&&!T-nextsibling)count++;if(T-firstchild)leafcount(T-firstchild,count);if(T-nextsibling)leafcount(T-nextsibling,count);}//leafcout//binsearch