数据结构考试题

《数据结构考试题》由会员分享，可在线阅读，更多相关《数据结构考试题（21页珍藏版）》请在装配图网上搜索。

1、一、单项选择1 .数据结构是一门研究非数值计算的程序设计问题中 ，数据元素的C 、数据信息在计算机中的 A 以及一组相关的运算等的 课程。A .操作对象B .计算方法C .逻辑结构D,数据映象A.存储结构B .关系C .运算D .算法2 .以下数据结构中,D 是线性结构。A .广义表 B .二叉树 C .稀疏矩阵C 两大类。B .顺序结构和链式结构D.初等结构和构造型结构3 .从逻辑上可以把数据结构分为A .动态结构和静态结构C.线性结构和非线性结构4 .以下数据结构中,D 是线性结构。A .广义表B .二叉树C .稀疏矩阵D .用5 .以下数据结构中,D一 是非线性结构。A .栈B .二叉树

2、C.队列D.字符串6 .数据结构DS(Data Struct)可以被形式地定义为DS=(D, R),其中D是B 的有限集合.R是D上的D 有限集合A,算法B.数据元素C.数据操作D.数据对象A.操作B .映象C.存储D.关系7 .线性表的顺序存储结构是一种A 的存储结构，线性表的链式存储结构是一种的B存储结构。A.随机存取B.顺序存取C.索引存取 D.散列存取8 .线性表的逻辑顺序与存储顺序总是一致的，这种说法A.正确 B.不正确9 .下面那一条是顺序存储结构的优点？ (A)A .存储密度大 B. 插入运算方便 C.删除运算方便D.可以方便的用于各种逻辑结构的存储表示10 .线性表采用链式存储

3、结构时,要求内存中可用的存储单元的地址A .必须是连续的 B.部分地址必须是连续的C. 一定不连续D.连续和不连续都可以11 .表长为n的顺序存储的线性表，当在任何位置上插入和删除一个元素的概率相等时，插入一个元素所需要移动元素的平均次数为 E ,删除一个元素所需要移动元素的平均次数为AA. (n-1)/2 B.n C. n+1 D. n-1 E. n/2 F. (n+1)/2 G. (n-2)/212 .带头结点的单链表head为空的判定条件是 B 。A. head= =NULL B. head-next= =NULLC. head-next= =head D. head!=NULL13 .

4、在一个单链表中，若删除p所指向结点白后继结点，则执行_AA. p-next= p-next-next B. p=p-next; p-next= p-next-nextC. p= p-next-next D. p= p-next14 .若已知一个栈的入栈序列是1, 2, 3,，n,其输出序列为p1, p2, p3,，pn,若p1=n,则pi为A. i B. n=i C. n-i+1 D.不确定15 .设栈的输入次序为:1 , 2, 3, 4, 5, 则 不可能是其出栈序列二A.54321 B.45321 C.43512 D.1234516 . 一个递归算法必须包括 BA.递归部分B.终止条件和递

5、归部分C.迭代部分D.终止条件和迭代部分17 .用链接方式存储的队列，在进行删除操作时DA仅修改头指针B.仅修改尾指针C.头尾指针都要修改D.头尾指针可能都要修改18 .数组Am存放循环队列的元素，其头尾指针分别是front和rear,则当前队列的元素个数是_AA. (rear-front+m)%m B. (front-rear+m)%m C. front-rear+1 D. rear-front+119 .栈和队列的共同特点 C 。A.都是先进先出B.都是先进后出C.允许在端点插入和删除元素D.没有共同点20 . 一个栈的入栈序列a, b, c, d, e,则栈的输出序列是 _AA. edc

6、ba B.decba C.dceab D.abcde21 .栈的特点是_B一队列的特点是_AA.先进先出B.先进后出22 .从一个栈顶指针HS的链表中删除一个结点，用x保存被删除的结点值，执行的语句为_C-A. x=HS; HS=HS-next B. HS=HS-next; x=HS-data23.在链队列Q中,A. Q.front-next=s;C. s-next=Q.rear;Q.rear=s插入s所指向的结点执行的语句为 CC. x=HS-data; HS=HS-next D. HS-next=HS; x=HS-dataB. Q.rear-next=s; Q.rear=sD. s-nex

7、t=Q.front;Q.front=s24 .空用与空格用是相同的，这种说法 _B_0A.正确 B. 不正确25 .下面关于用的叙述，哪一个是不正确的_BA.用是字符的有限序列B. 空用是由空格构成的用C.匹配模式是用的一种重要运算D.用可以采用链式存储结构26 .设有两个用p和q,求q在p中首次出现的位置的运算称作_B_0A.连接B.模式匹配C.求子用D.求用长27 .若用s=software,其子用的数目为 BA. 8 B. 37 C. 36 D. 928 .二维数组A中，每个元素A的长度为3个字节，行下标i从0到7,列下标j从0到9,从首地址SA开始连续存放在存储器内, 该数组按行存放时

8、，数组元素A74的起始地址为_CA. SA+141 B. SA+144 C. SA+222 D. SA+22529 .对稀疏矩阵进行压缩存储的目的是_C_.A.便于进行矩阵运算B.便于输入输出C节省存储空间D.降低运算的时间复杂度30 .在以下叙述中正确的是 BA.线性表的线性存储结构优于链表存储结构B.二维数组可以看成是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出31 .广义表(a),a)的表头为 C , 表尾为C .A. () B. a C. (a) D. (a)32 .已知广义表L=(x,y,z),a,(u,t,w), 从L中取出原子项t的运算为_D,

9、A. Head(Tail(Tail(L) B. Tail(Head(Head(Tail(L)C. Head(Tail(Head(Tail(L) D. Head(Tail(Head(Tail(Tail(L)数据之间具有分支层次关系的数据 无太多关系的数据元素33 .树最适合用来表示BA.有序的数据元素B.C.无序的数据元素D.34 .如果某二叉树的前根次序遍历结果为stuwv,中序遍历为uwtvs,那么该二叉树的后序为_B.A. uwvts B. vwuts C. wuvts D. wutsv35 .某二叉树的前序遍历结点访问顺序是abdgcefh ,中序遍历的结点访问顺序是 dgbaechf,

10、则其后序遍历的结点访问顺序是 D,A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca36 .在一非空二叉树的中序遍历序列中，根结点的右边 _AA.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的部分结点D.只有左子树上的所有结点37 .设m和n是一棵二叉树上的两个结点,在中序遍历，n在m前的条件是 CA. n在m的右方B. n是m的祖先C. n在m的左方D. n是m的子孙38 .深度为5的二叉树至多有_C结点A. 16 B. 32 C. 31 D. 1039 .由权(8,2,5,7)的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度

11、为 DA. 23 B. 37 C. 46 D. 4340 .利用二叉链表存储树，则根结点的右指针是 CA.指向最左孩子B.指向最右孩子C. 空 D. 非空41 .下列存储方式中，哪一个不是树的存储形式？ DA.双亲表示法 B.孩子链表表示法 C.孩子兄弟表示法D. 顺序存储表示法42 .在一个无向图中，所有顶点的度数之和等于所有边数的_C。A. 1/2 B. 1 C. 2 D. 443 .具有n个顶点和多于n-1条边的无向图B .A.有可能是树 B. 一定不是树 C. 一定是树 D. 以上答案都不对44 .具有6个顶点的无向图至少应有A条边才能确保是一个连通图。A. 5 B. 6 C. 7 D

12、. 845.无向图 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),则对该图进行深度优先遍历，得到的序列为：DA. abecdf B. acfebd C. aebcfd D. aedfcb46 .下述几种排序方法中，要求内存量最大的是 _D-A.插入排序 B. 选择排序 C. 快速排序 D.归并排序47 .排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上 的方法，称为_CA.希尔排序 B. 起泡排序 C.插入排序D.选择排序48 .在待排序的

13、元素序列基本有序的前提下，效率最高的排序方法是_A_0A.插入排序B.选择排序 C. 快速排序 D.归并排序49 .下列排序算法中，哪一个是稳定的排序算法？ BA.直接选择排序 B.二分法插入排序 C.希尔排序D.快速排序50 .将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数 AA. n B. 2n-1 C. 2n D. n-1二、填空题1 .算法的五个重要特性是有穷性，确定性，可行性,输入和输出.2 .数据的树型结构和图（网）状结构合称非线性结构.3 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与 数据在计算机中的表示和实现无关.4 .评价算法质量的指标是 正确性，易读性，

14、健壮性，高效性.5 .数据结构中评价算法的两个重要指标是:时间复杂度和空间复杂度.6 .分析下面算法(程序段)，的时间复杂度是 O (mn) 。s=0;for (i=0;in;i+)for (j=0;jprior=q-prior;q-prior-next=p;p-next=q;q-prior=p;16 . 一般情况下，将递归算法转换成等价的非递归算法应该设置栈.17 .在解决计算机主机与打印机速度不匹配问题时，通常设置一个打印数据缓冲区，该缓冲区通常是一个 队列 数据结构.18 .循环队列的引入，目的是为了克服假溢出 现象.19 .在栈顶指针为HS的链栈中，判断栈空的条件是HS=NULL .2

15、0 .在具有n个单元的循环队列中,如果不专门设置队满标志,则队满时共n-1有个元素.21 .实现字符串拷贝的函数如下,请补足Void strcpy(char *s, char *t)while( (*s+=*t+)!=0)；22 .空格用是由一个或多个空格字符组成的成,其长度等于 其包含的空格个数。23 .空串是 不包含任何字符的毛， 其长度为0 .24 .设 s=I AM A STUDENT,其长度为：14 .25 .组成用而元豪只能是:字符.26 .设 s1=Good, s2=, s3=bye!, 贝U s1,s2 和 s3 连接的结果是 Good bye!27 .若广义表中每个元素都是原

16、子时，广义表便成为 线性表.28 .广义表的表尾是指除第一个元素外，剩余元素组成的表.29 .广义表A=(a,b,c,d) 的表头为(a,b,c,d), 表尾为().30 .数组的存储结构采用顺序存储方式.31 .设二维数组a0.5, 0.6,其每个字节占5个字节，第一个元素的存储地址为1000,若按列存储，则元素a5,5存储地址为1175 .32 .高度为k的完全二叉树至少有2k 2 个叶子结点.33 .若一棵二叉树有50个叶子结点，则该二叉树的总结点数至少是_99_34 .有n个叶子结点的哈夫曼树的结点总数为2n-1.35 .根据二叉树的定义，具有三个结点的二叉树有_4一种.36 .某棵二

17、叉树的中序遍历序列为abcdefg,后序遍历序列为bdcafge,则该二叉树的前序遍历序列eacbdgf ,该二叉树对应的森林包含2 棵二叉树.37 .若二叉树采用二叉链表存储结构，要交换其所有分支结点的左，右子树的位置，利用 中序遍历方法最为合适.38 .线索二叉树的左线索指向其前驱，右线索指向其 后继.39 .树所对应的二叉树其根结点的右子树一定为空.40 .利用树的孩子兄弟表示法存储，可以将一棵树转化成二叉树.41 .设无向图的顶点个数为n,则该图最多有n(n-1)/2 条边.42 . n个顶点的连通图至少有n-1 条边.43 .已知一个图用领接矩阵表示，计算第i个结点的入度的方法是求第

18、i列非零元素的和.44 . G是一个非连通的无向图,共有28条边，则该图至少有/个顶点.45 . 一个图的邻接矩阵 表示法是唯一的,而 邻接表 表示法是不唯一的。0 1 046 .从邻接矩阵A 1 0 1可以看出，该图共有色 个顶点，如果是无向图，则共有上0 1 047 . n个顶点的连通图用邻接矩阵表示时，则该矩阵至少有2(n-1)个顶点.48 .设图中有n个顶点，e条边，如果用邻接表表示图，进行深度优先搜索遍历的时间复杂度为 间复杂度为O(n2)49 .从平均时间性能而言，快速排序排序最隹.50 .堆排序是一种 选择排序,堆实质上是一棵完全二叉树结点的层次序列.对于含有nO(log2n).

19、所需附加的存储结点是0(1).三、用图表回答下列问题1 .设某通信系统使用A, B , C, D, E, F, G, H个字符，出现的频率 w=5 ,2 9, 造对应的哈夫曼树(请按左子树根结点的权小于右子树树根结点的权的次序构造)？一条边.O(n+e),如果用邻接矩阵表示图，时个元素的排序,堆排序的时间复杂度为,8,14,23,3,11,试构答案如图：1004258F29B192329DHE1581114精品资料v1v2|v2 |一 v5 I 一v3v4 A答案如图所ZV1: 3V2: 2V3: 3V4: 2V5: 4V6: 2v3 :v4v5v6v4 v4v1v3v5v2v32.根据下面的

20、邻接链表，画出相应的图，写出每个顶点的度 ，并用邻接矩阵表示0 10 1100010000000010000000011010000003.画出下列树对应的二叉树，并写出其先根遍历序列:ABCDFE先根遍历序列：A B D E G F C答案如图所示：A4.画出和下列二叉树对应的森林:四、阅读下列算法，按要求做答.1.下面是删除单链表L中最大元素所在结点的类C语言算法，请补足缺失部分使其完整 void DelMax(LinkList L)r=L; p=L-next; if(p)m=p-data; (1); p=p-next;while(p) if(2)_)(3); m=p-data;(4);

21、p=p-next; q=r-next; (5); free(q); 答案：(1) L-next=NULL ; (2)p!=NULL; (3)q!=NULL ; (4) p-next=r-next (5) r-next=p.2 .阅读下列算法，说明该算法的作用。Status algorithm1(LinkQueue &Q)SqStack Stack;QElemType Element;InitStack(Stack);while(!QueueEmpty(Q)DeQueue(Q,Element);Push(Stack,Element);while(!StackEmpty(Stack)Pop(Sta

22、ck,Element);EnQueue(Q,Element);答：利用栈实现队列的逆置.3 .阅读下列算法，说明该算法的作用。Status algorithm2(Stack S, int e)Stack T;int d;InitStack(T);while(!StackEmpty(S)Pop(S,d);if(d!=e) Push(T,d);while(!StackEmpty(T)Pop(T,d);Push(S,d);答：利用辅助栈T,将栈S中的元素e删除.4 .将下面程序改写成递归过程.void algorithm3(int n)int i=n;while(i1) printf(i-);voi

23、d algorithm4(int j) if(j1)printf(j);algorithm4(j-1)5 .阅读下列算法，说明该算法的作用BiTree algohthm5(ElemType Pre口，ElemType In儿int PreLen, InLen;int i, j；BiTree BT;ElemType *subPre, *subIn;PreLen = strlen(Pre);InLen = strlen(In);if (PreLen != InLen | PreLen = 0) return NULL;for (i=0; idata = Pre0;subPre = (ElemTyp

24、e *) malloc(i+1)*sizeof(ElemType);subIn = (ElemType *) malloc(i+1)*sizeof(ElemType);for (j=0; jlchild = CreatBT(subPre, subin);subPre = (ElemType *) malloc(PreLen-i)*sizeof(ElemType); subin = (ElemType *) malloc(PreLen-i)*sizeof(ElemType);for (j=i+1; jvPreLen; j+)subPrej-i-1 = Prej;subinj-i-1 = Inj;

25、subPrej-i-1 = 0; subinj-i-1 = 0;BT-rchild = CreatBT(subPre, subin);return BT;答：利用一棵二叉树的先序遍历和中序遍历还原该二叉树 .五、算法设计题1 .设顺序表L中的数据元素递增有序.试写一个算法，将e插入顺序表中，要求插入后保持该表的有序性 void InsertElem(SqList &L, ElemType)j=L.length-1;while(L.elemje)L.elemj+1=L.elemj; j+L.elemj+1=e;L.length+;2 .已知la是带头结点的单链表的头指针，试编写一个逆序输出表中各

26、个元素的递归算法void TraverseLink(LinkList p)if(p-next) TraverseLink(p-next);printf(p-data);3 .写一算法，统计二叉树的结点的总个数。/利用中序遍历方法，或者先序、后序均可以中根遍历左子树 计算结点中根遍历右子树void Leaf(BiTree T, int &m) if (T!=NULL) Leaf(T-lchild, m); / m+;/Leaf(T-rchild, m); / 4 .写一算法，求二叉树的高度int height(BiTree T) if (T = NULL) return 0;else int h

27、l=height(T-lchild);int hr=height(T-rchild);加上hl和hr的较大值return 1 + (hlhr?hl:hr); /15 .写一算法，交换二叉树的左右子树。BiTNode Permute_child(BiTNode *T)BiTNode *temp;if(T)Permute_child(T-lchild);Permute_child(T-rchild);temp=T-lchild;T-lchild=BT-rchild;T-rchild=temp;6 .已知二叉树采用二叉链表存储，设计算法，判定两棵二叉树是否相似Statues like(BiTree S, BiTree T) if(T=NULL & S=NULL) return 1;else if (S & T)return (like(S-lchild , T-lchild) & like(S-rchild , T-rchild);else return 0;