数据结构_模拟测验题全部(带答案).doc

题型： 填空题 （10题，每空1分，10分） 判断+改错 (5-10题，每题1-2分，10-20分) 选择题 （15-20题，每题1分，15-20分） 综合题 （5-7个大题，共35-40分） 程序题 （2-3题，共10-15分）综合题 二叉树的顺序存储，前、中、后、层序遍历方法 已知二叉树的前(后)序+中序遍历，画二叉树 给定一个权值集合，画哈夫曼树，求哈夫曼编码 图的邻接矩阵和邻接表存储、广度和深度遍历方法 Prim算法和Kruskal算法求无向带权图的最小生成树 给定待排序的数据序列，写出直接插入排序、希尔排序、直接选择排序、堆排序、 冒泡排序、快速排序的排序过程 二叉排序树的建立 哈希表的建立程序题 求带头结点的单链表长的算法 (显示单链表所有元素) 在单链表中查找内容为x的结点的算法 在带头结点head的单链表的结点a之后插入新元素x 删除单链表的第i个结点 直接插入排序 直接选择排序 冒泡排序 二分查找单元测验1一判断题（）（1）数据的逻辑结构和数据的存储结构是相同的。（）（2）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。（）（3）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。（）（4）数据的存储结构是数据的逻辑结构的存储映像。（）（5）数据的逻辑结构是依赖于计算机的。（）（6）算法是对解题方法和步骤的描述。二填空题1数据有逻辑结构和存储结构两种结构。2. 数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。3树形结构和图形结构合称为非线性结构。4数据的存储结构又叫物理结构。5数据的存储结构形式包括：顺序存储和链式存储6线性结构中的元素之间存在一对一的关系。7树形结构中的元素之间存在一对多的关系，8图形结构的元素之间存在多对多的关系。9数据结构主要研究数据的逻辑结构、存储结构和 二者之间的相互运算 三个方面的内容。10一个算法的时间复杂度是 问题规模 的函数。11若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为O（nlog2n）。12若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为O（n2）。三选择题1数据结构通常是研究数据的（ D ）及它们之间的相互联系。A.联系与逻辑 B.存储和抽象 C.联系和抽象 D.存储结构和逻辑结构2数据在计算机内存储时，数据元素在存储器内相对位置可以表示元素之间的逻辑关系，称为（D）。A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构3链接存储的存储结构所占存储空间（A）。A分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针B只有一部分，存放结点值C只有一部分，存储表示结点间关系的指针D分两部分，一部分存放结点值，另一部分存放结点所占单元数4在数据结构中，与所使用的计算机无关的是（B）A.物理结构 B.逻辑结构 C.存储结构 D.逻辑和存储结构5算法能正确的实现预定功能的特性称为（A）A.正确性B.易读性C.健壮性D.高效性6算法在发生非法操作时可以作出处理的特性称为（B）A.正确性 B.健壮性 C.易读性D.高效性7下列时间复杂度中最坏的是（A）A.O（n2）B.O（log2n）C.O（n）D.O（1）8. 算法分析的两个主要方面是（C）。A.可读性和文档性B.正确性和简明性C.空间复杂性和时间复杂性D.数据复杂性和程序复杂性四分析下面各程序段的时间复杂度（1）s=0;for(i=0;in;i+)for(j=0;jn;j+)s= s+Bij;（2）for (i=0;in;i+)for (j=0;inext!=NULL) ; ;return n;2、在单链表中查找内容为x的结点的算法：Node * Lsearch ( linknode *head, char x)P=head;while (P-next!=NULL & P-data!= x ) ; if ( ) printf ( 没有找到! n);elsereturn P; /*找到，返回结点指针*/3、在带头结点head的单链表的结点a之后插入新元素x： struct NodeChar data;Node *next;void ListInsert (Node *head, Char x)node *p,*s;p=head-next;while (p!=NULL) & ( p-data!=a ) ;if (p= =NULL)printf ( 不存在结点a，无法插入! n); elses= ;s-data= ;_ _;_ _ _ _;单元测验3一判断题（）（1）栈是运算受限制的线性表。（）（2）在栈空的情况下，不能作出栈操作，否则产生下溢出。（）（3）栈一定是顺序存储的线性结构。（）（4）栈的特点是“后进先出”。（）（5）链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。 （）（6）一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。二填空题1在栈结构中，允许插入、删除的一端称为 栈顶 。 2在一个链栈中，若栈顶指针等于NULL，则表示 栈空 。 3已知顺序栈S，在对S进行出栈操作之前首先要判断 栈是否空 。4从一个栈删除元素时，首先取出栈顶元素，然后再移动 栈顶指针 。5. 顺序栈用datan存储数据，栈顶指针是top, 则值为x的元素入栈的操作是_ datatop=x；top+；三选择题 1设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的站台，下列不可能的出站顺序为 ( B )A1234 B1423 C1324 D12432顺序栈存储空间的实现使用（ B ）存储栈元素。A链表 B数组 C循环链表 D变量 3如果以链表作为栈的存储结构，则出栈操作时（ B ） A必须判别栈是否满 B必须判别栈是否空C必须判别栈元素类型 D队栈可不做任何判别 4一个栈的入栈次序ABCDE，则栈的不可能的输出序列是 ( D )。 AEDCBA BDECBA CABCDE DDCEAB 5、栈与一般线性表的区别在于 ( C )。 A数据元素的类型不同 B数据元素的个数不同C操作是否受限制 D逻辑结构不同HeadAa0BD/C6带头结点的链栈LS的示意图如下，栈顶元素是（ A ）AA BB CC DD单元测验4一判断题（）（1）队列是限制在两端进行操作的线性表。（）（2）判断顺序队列为空的标准是头指针和尾指针均指向同一个结点。（）（3）在循环链队列中无溢出现象。（）（4）栈和队列都是顺序存储的线性结构。（）（5）在队列中允许删除的一端称为队尾。（）（6）顺序队列和顺序循环队列的队满和队空的判断条件是一样的。 二填空题 1在队列中存取数据应遵从的原则是 先进先出 。 2在队列中，允许插入的一端称为 队尾 。 3对于队列，只能在 队首 删除元素。4解决顺序队列“假溢出”的方法是采用 循环队列 。 5顺序队列的队头指针为front，队尾指针为rear，则队空的条件为 front = rear 。 6在一个链队列中，若队头指针与队尾指针的值相同，则表示该队列为 空 。 7区分循环队列的满与空，有三种方法，它们是_设计数器_、_设标志位_和_少用一个存储空间_。8. 循环队列存储在数组Am中，则入队时的操作为rear=(rear+1) % m9设顺序循环队列的队头指示器front指向队头元素，队尾指示器rear指向队尾元素后的一个空闲元素，队列的最大空间为M，则用牺牲一个存储单元区分队列满与空时，队满标志为 front=(rear+1)% M 。10. 已知链队列的头尾指针分别是Q-front和Q-rear，则将值x入队的操作序列是p = (LQNode *)malloc(sizeof(LQNode)； p-data=x; p-next=NULL；Q-rear-next=p；Q-rear = p；三选择题 1同一队列内各元素的类型( A )。 A必须一致 B不能一致 C不限制 D可以不一致 2队列是一个( D )线性表结构。 A不加限制的 B推广了的 C非 D加了限制的3四个元素按：A，B，C，D顺序连续进队Q，执行一次出队操作后，队头元素是（ C ）。 ADBC C BD A4若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为 ( B )。 A5和1 B4和2 C2和4 D1和55以下属于队列的操作有( D )。 A在队首插入元素 B删除值最小的元素 C按元素的大小排序 D判断是否还有元素6. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( C )。A 6 B. 4 C. 3 D. 2单元测验5一、选择题1. 若对n阶对称矩阵A (行下标和列下标范围均为1n)，将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B0.(n(n+1)/2-1中，则在B中确定aij（i C1，2） D2 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的( B )倍。A1/2 B. 1 C. 2 D. 43 对于一个具有n个顶点的无向图的边数最多有（ B ）。 An Bn（n-1）/2 Cn（n-1） D2n4在一个具有n个顶点的无向图中，要连通全部顶点至少需要（ B ）条边。 An Bn-1 Cn+1 Dn/25 有8个结点的有向完全图有( C )条边。A14 B. 28 C. 56 D. 1126 无向图顶点v的度是关联于该顶点（ B ）的数目。 A顶点 B边 C序号 D下标 7有n个顶点的无向图的邻接矩阵是用（ B ）数组存储。A一维 Bn行n列 C任意行n列 Dn行任意列 8在一个具有n个顶点e条边的图中，所有顶点的度数之和等于（ C ）。 Ae B n C2e D2n四应用题1 根据如下无向图（1） 画出该图的邻接矩阵和邻接表（2） 并分别给出该图邻接矩阵下的深度优先搜索遍历和广度优先搜索遍历的结点序列。2 分别用普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法画出构造该无向带权图最小生成树的过程。单元测验8一判断题（）（1）如果某种排序算法不稳定，则该排序方法就没有实际应用价值。（）（2）对n个记录的进行快速排序，所需要的平均时间是O（nlog2n）。（）（3）堆排序所需的时间与待排序的记录个数无关。（）（4）当待排序的元素个数很多时，为了交换元素的位置要占用较多的时间，这是影响时间复杂度的主要因素。（）（5）对快速排序来说，初始序列为递增有序或递减有序都是最坏情况。（）（6）采用希尔方法排序时，若关键字的排列杂乱无序，则效率较高。 二填空题1大多数排序算法都有两个基本的操作： 比较 和移动。 2对n个关键字进行冒泡排序，时间复杂度为 O（n2） 。 3快速排序在最坏情况下的时间复杂度是 O（n2） 。 4在排序前，关键字值相等的不同记录，排序后相对位置保持 不变 的排序方法，称为稳定的排序方法。 5当增量为1时，该趟希尔排序与 直接插入 排序基本一致。 6第一趟排序后，序列中键值最大的记录交换到最后的排序算法是 冒泡排序 。 7依次将待排序的每个记录插入到一个有序已排序序列中的排序方法称为 插入 排序。 8对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 3 次。 9两个序列分别为： L1=25，57，48，37，92，86，12，33 L2=25，37，33，12，48，57，86，92。用冒泡排序法对L1和L2进行排序，交换次数较少的是序列： L2 。10对一组记录（54，35，96，21，12，72，60，44，80）进行直接选择排序时，第四次选择和交换后，未排序记录是 54，72，60，96，80 。 三选择题1排序是根据（ A ）的大小重新安排各元素的顺序。 A关键字 B数组 C元素件 D结点 2排序方法中，从无序序列中选择关键字最小的记录，将其与无序区（初始为空）的第一个记录交换的排序方法，称为 ( B )。 A插入排序 B选择排序 C希尔排序 D. 快速排序3每次把待排序方的区间划分为左、右两个区间，其中左区间中元素的值不大于基准元素的值，右区间中元素的值不小于基准元素的值，此种排序方法叫做（ D ）。 A冒泡排序 B堆排序 C希尔排序 D.快速排序4快速排序在（ C ）情况下最易发挥其长处。 A待排序的数据中含有多个相同的关键字 B待排序的数据已基本有序 C待排序的数据完全无序 D待排序的数据中最大值与最小值相差悬殊 5直接插入排序的方法是从第（ B ）个元素开始，插入到前边适当位置的排序方法。 A1 B2 C3 Dn6堆的形状是一棵（ C ）。 A二叉排序树 B满二叉树 C完全二叉树 D任意二叉树7内排序是指在排序的整个过程中，全部数据都在计算机的（ A ）中完成的排序。A内存 B外存 C内存和外存 D寄存器8下述几种排序方法中，平均时间复杂度最小的是（ A ）。A希尔排序 B直接插入排序 C冒泡排序 D直接选择排序 9对n个数据进行快速排序，在最坏情况下，算法的时间复杂度是（ B ）。 AO(n) BO(n2) CO(nlog2n) DO(n3)10冒泡排序的方法对n个数据进行排序，第一趟排序共需要比较（ C ）次。 A1 B2 Cn-1 Dn11用直接插入排序法对下面的四个序列进行由小到大的排序，元素比较次数最少的是（ B ）。 A，94，32，40，90，80，46，21，69 B21，32，46，40，80，69，90，94C32，40，21，46，69，94，90，80 D90，69，80，46，21，32，94，4012 一个数据序列的关键字为：（46，79，56，38，40，84），采用快速排序，并以第一个数为基准得到第一次划分的结果为：（ C ） A（38，40，46，56，79，84） B（40，38，46，79，56，84） C（40，38，46，56，79，84） D（40，38，46，79，56，84） 四应用题1 已知数据序列80，18，9，90，27，75，42，69，试写出采用冒泡排序（从小到大）算法排序时，每一趟排序的结果。2 已知数据序列40，63，11，84，35，93，58，39，试写出采用直接选择排序（从小到大）每一趟排序结果。3 已知数据序列12，2，16，30，28，10，17，20，写出希尔排序（从小到大）每一趟（设d=4,2,1）的排序结果。4 已知数据序列10，1，15，18，7，15，试写出采用快速排序（从小到大）每一趟排序的结果。5 已知数据序列18，17，60，40，07，32，73，65，试写出采用直接插入排序（从小到大）每一趟排序结果。五程序填空1 直接选择排序 2、直接插入排序3、冒泡排序单元测验9一判断题（）（1）二分查找法要求待查表的关键字值必须有序。（）（2）对有序表而言采用二分查找总比采用顺序查找法速度快。（）（3）在二叉排序树中，根结点的值都小于孩子结点的值。（）（4）哈希表是一种将关键字转换为存储地址的存储方法。（）（5）哈希法的查找效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。（）（6）在二叉排序树上删除一个结点时，不必移动其它结点，只要将该结点的父结点的相应的指针域置空即可。 二填空题 1在分块查找方法中，首先查找 索引表 ，然后再查找相应的块。 2顺序查找、二分查找、分块查找都属于 静态 查找。 3对于长度为n的线性表，若进行顺序查找，则时间复杂度为 O（n） 。 4对于长度为n的线性表，若采用二分查找，则时间复杂度为： O（log2n） 。 5在关键字序列（7，10，12，18，28，36，45，92）中，用二分查找法查找关键字92，要比较 4 次才找到。 6对二叉排序树进行查找的方法是用待查的值与根结点的键值进行比较，若比根结点小，则继续在 左 子树中查找。 7二叉排序树是一种 动态 查找表。 8哈希法既是一种存储方法，又是一种 查找 方法。 9设哈希函数H(k)和键值k1，k2，若k1k2，且H（k1）=H（k2），则称这种现象为 哈希冲突 。 10处理冲突的两类主要方法是开放定址法和 链表法 。11在哈希函数H(key)=key % P中，P一般应取 质数 。 12在查找过程中有插入元素或删除元素操作的，称为 动态 查找。 三选择题 1对线性表进行二分查找时，要求线性表必须 （ B ）。A以顺序方式存储 B以顺序方式存储，且结点按关键字有序排序C以链接方式存储 D以链接方式存储，且结点按关键字有序排序2衡量查找算法效率的主要标准是（ C ）。A元素个数 B.所需的存储量 C平均查找长度 D算法难易程度 3有一个有序顺序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当