数据结构考试题及答案

hgkghkghkghkghk

一、选择题 2012年数据结构期末考试题及答案1．在数据结构中，从逻辑上可以把数据结构分为 C 。A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构2．数据结构在计算机内存中的表示是指 A 。A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。A．逻辑 B．存储 C．逻辑和存储 D．物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。A．数据的处理方法 B．数据元素的类型C．数据元素之间的关系 D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑 A 。A．各结点的值如何 B．结点个数的多少C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。6．以下说法正确的是 D 。A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性C．可读性和文档性 D．数据复杂性和程序复杂性8．下面程序段的时间复杂度是 O（n2） 。s ＝0；for（ I ＝0； i＜n； i＋＋）for（j＝0；j＜n；j＋＋）s ＋＝B[i][j]；sum ＝ s ；9．下面程序段的时间复杂度是 O（n*m） 。for（ i ＝0； i＜n； i＋＋）for（j＝0；j＜m；j＋＋）A[i][j] ＝ 0；10．下面程序段的时间复杂度是 O（log3n） 。i ＝ 0；while（i＜＝n）i ＝ i * 3；11．在以下的叙述中，正确的是 B 。A．线性表的顺序存储结构优于链表存储结构B．二维数组是其数据元素为线性表的线性表C．栈的操作方式是先进先出D．队列的操作方式是先进后出12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 B 。A．数据元素具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等。

《数据结构》期末考试试卷（ A ）一、 选择题（每小题2分，共24分）1．计算机识别、存储和加工处理的对象被统称为( A )A.数据 B.数据元素C.数据结构 D.数据类型2．栈和队列都是（ A ）A．限制存取位置的线性结构 B．顺序存储的线性结构C．链式存储的线性结构 D．限制存取位置的非线性结构 3．链栈与顺序栈相比，比较明显的优点是( D )A.插入操作更加方便 B.删除操作更加方便C.不会出现下溢的情况 D.不会出现上溢的情况4．采用两类不同存储结构的字符串可分别简称为( B )A.主串和子串 B.顺序串和链串C.目标串和模式串 D.变量串和常量串5． 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是：BA. 110 B .108C. 100 D. 120 6．串是一种特殊的线性表，其特殊性体现在：BA.可以顺序存储 B .数据元素是一个字符C. 可以链接存储 D. 数据元素可以是多个字符7．设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为： CA. 2h B .2h-1C. 2h+1 D. h+1软件开发网 ．树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把 由树转化得到的二叉树叫做这棵树对应的二叉树。下列结论哪个正确？ AA. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同B .树的后根遍历序列与其对应的二叉树的后序遍历序列相同C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同D. 以上都不对9．一个有n个顶点的无向图最多有多少边？CA. n B .n(n-1)C. n(n-1)/2 D. 2n10．在一个图中，所有顶点的度数之和等于所有边数的多少倍?CA. 1/2 B .1C. 2 D. 4 11．当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为（ A ）A．左子树的叶子结点 B．左子树的分支结点C．右子树的叶子结点 D．右子树的分支结点软件开发网 ．对于哈希函数H(key)=key%13,被称为同义词的关键字是( D )和41 和和44 和51 二、已知某棵二叉树的前序遍历结果为A,B,D,E,G,C,F,H,I,J，其中中序遍历的结果为D,B,G,E,A,H,F,I,J,C。请画出二叉的具体结构。（注意要写出具体步骤）（10分）原理见课本128页三、有图如下，请写出从顶点c0出发的深度优先及宽度优先遍历的结果。(10分) 深度优先；C0-C1-C3-C4-C5-C2宽度优先：C0-C1-C2-C3-C4-C5四、有图如下，按Kruskal算法求出其最小生成树。要求写出完整的步骤。（10分）原理见课本250页五、给定线性表（12，23，45，66，76，88，93，103，166），试写出在其上进行二分查找关键字值12，93，166的过程。并写出二分查找的算法。（20分）0 1 2 3 4 5 6 7 812 23 45 66 76 88 93 103 166过程：mid=(0+8)/2=4high=3,low=0 mid=1high=0,low=0 mid=0（找到12）high=8,low=5,mid=6（找到93）high=8,low=7,mid=7high=8 low=8 mid=8算法：见课本84页上六、知单链表的结点结构为Data next下列算法对带头结点的单链表L进行简单选择排序，使得L中的元素按值从小到大排列。请在空缺处填入合适的内容，使其成为完整的算法。 (可用文字说明该算法的基本思想及执行的过程，10分)void SelectSort(LinkedList L){ LinkedList p,q,min; DataType rcd; p= (1) ; while(p!=NULL) { min=p; q=p->next; while(q!=NULL){ if( (2) )min=q; q=q->next; } if( (3) ){ rcd=p->data; p->data=min->data; min->data=rcd; } (4) ; }} 本题不会。嘿嘿。。。。七、一个完整的算法应该具有哪几个基本性质？分别简要说明每一性质的含意。(5分) 输入：四个基本性质：1.输入：有零个或多个有外部提供的量作为算法的输入 2：输出：算法产生至少一个量作为输出 3.：确定性：组成算法的每条指令是清晰的，无歧异的。 4.：有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的八、何谓队列的"假溢"现象？如何解决？（5分）队列的假溢现象是指数组实现的顺序队列中，队尾指针已到达数组的下表上界产生上溢而队头指针之前还有若干 空间闲置的现象。解决的办法之一是利用循环队列技术使数组空间的首尾相连。 九、说明并比较文件的各种物理结构。（6分）