《数据结构考试文.docx》由会员分享，可在线阅读，更多相关《数据结构考试文.docx（6页珍藏版）》请在三一办公上搜索。
1、数据结构考试文一、单项选择题 1若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为 A顺序 B链式 C索引 D散列 2在长度为N的顺序表的第I个位置上插入一个元素，元素的移动次数为 An-I+1 Bn-I CI DI+1 3对于只在表的首，尾两端进行插入操作的线性表，宜采用的存储结构为 A顺序表 C用尾指针表示的单循环链表 A4 B5 B用头指针表示的单循环链表 D单链表 C6 D7 4若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为 5为查找某一特定单词在文本中出现的位置，可应用的串运算是 A插入B删除C串联接D子串定位 6如下陈述中正确的是 A串
2、是一种特殊的线性表 C串中元素只能是字母 B串的长度必须大于零 D空串就是空白串 7若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是( ) A9 B11 C12 D不确定 8按二叉树的定义，具有3个结点的二叉树有( )种。 A3 B4 C5 D6 9假设以带行表的三元组表表示稀疏矩阵，则和下列行表 10在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( ) A4 B5 C6 D7 11在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( ) Ae B2e Cn2e Dn22e 12假设一个有n个顶点和e条弧的有向图用邻接表表示,则删
3、除与某个顶点vi相关的所有弧的时间复杂度是( ) 1 AO(n) BO(e) CO(n+e) DO(n*e) 13用某种排序方法对关键字序列进行排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是 A选择排序 B希尔排序 C归并排序 D快速排序 14适于对动态查找表进行高效率查找的组织结构是 A有序表 B分块有序表 C三叉排序树 D线性链表 15不定长文件是指 A文件的长度不固定 C字段的长度不固定 二、填空题 16数据的逻辑结构是从逻
4、辑关系上描述数据，它与数据的_无关，是独立于计算机的。 B记录的长度不固定 D关键字项的长度不固定 17在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=_。 18栈顶的位置是随着_操作而变化的。 19在串S=“structure”中，以t为首字符的子串有_个。 20假设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中，其中B0存储矩阵中第1个元素a11，则B31中存放的元素是_。 21若一个算法中的语句频度之和为T(N)=3720N+4NLOGN,则算法的时间复杂度为( ） 22在在树中，度为( )的结点称为叶子。 23假设以S和X
5、分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为 24串S=”I AM A WORKER”的长度是 2 25对关键字序列进行一趟快速排序之后得到的结果为 三、解答题 26已知一个6行5列的稀疏矩阵中非零元的值分别为：-90,41,-76,28,-54,65和-8，它们在矩阵中的列号依次为1，4，5，1，2，4和5，当以带行表的三元组表作存储结构时，其行表RowTAB中的值依次为0，0，2，2，3和5，请写出该稀疏矩阵 27已知树T的先序遍历序列为ABCDEFGHIJKL,后序遍历序列为CBEFDJIKLHGA,请画出树T， 28对
6、关键字序列进行堆排序，使之按关键字递减次序排列，请写出排序过程中得到的初始堆和前三趟的序列状态。 29在关键字序列中用二分查找法查找和给定值92相等的关键字，请写出查找过程中依次和给定值92比较的关键字。 3 四、算法阅读题 30设栈S=(1,2,3,4,5,6,7)其中7为栈顶元素。请写出调用algo(&S)后栈S的状态 void algo(Stack *S) int i=0; Queue Q;Stack T; InitQueue(&Q);InitStack(&T); While(!StackEmpty(S) if(i=!i)!=0)Push(&T,Pop(&S); else EnQueue
7、(&Q,Pop(&S); while(!QueueEmpty(Q) Push(&S,DeQueue(&Q); While(!StackEmpty(T) Push(&S,Pop(&T); 31阅读下面的算法 LinkList mynote(LinkList L) /L是不带头结点的单链表的头指针 if(L&Lnext) q=L；L=Lnext；p=L； S1： while(pnext) p=pnext； S2： pnext=q；qnext=NULL； return L； 请回答下列问题： 说明语句S1的功能； 说明语句组S2的功能； 4 设链表表示的线性表为,写出算法执行后的返回值所表示的线性表。 答： 五、算法设计题 32假设二叉树T采用如下定义的存储结构； typedef struct node DataType data; struct node *lchild,*rchild,*parent; PBinTree,其中，结点的lchild和 rchild域巳分别填有指向其左、右孩子结点的指针，而parent域中的值为空指针。请编写一个递归算法，将该储结构中各结点parent域的值修改成指向其双亲结点的指针。 5
