数据结构基本复习题答案

第1章绪论1自测习题二、选择题．以下数据结构中，属于线性结构的是(B)A）有向图B）串）线索二叉树D）B树．下列与数据元素有关的叙述中错误的是(A)A）数据元素是有独立含义的数据最小单位B）数据元素是描述数据的基本单位）数据元素可以称做结点）数据元素可以称做记录．以下术语中与数据的存储结构无关的是(A)A）栈B）散列表）顺序表）双链表．以下数据结构中，属于线性结构的是(B)A）有向图B）串）线索二叉树D）B树三、填空题．数据结构包括的三方面内容分别是：数据的逻辑结构、数据感谢阅读的存储结构和数据的运算。结点、谢谢阅读记录和顶点。4种基本形态包括集合结构、线性结构、树精品文档放心下载型结构和图（网）结构。5、输出、感谢阅读可行性和有穷性。链式、索引和散列四种。精品文档放心下载．一个数据结构在计算机中的映象称为存储结构。7．一个算法的效率主要是指该算法的时间效率和空间效谢谢阅读率。．以下程序段的时间复杂度T（）=_O(n2)。感谢阅读sum=0;for(i=0;i<n;i++)for(j=0;j<n;j++)sum+=a[i][j];printf("%d\n",sum);第2章2自测习题二、选择题B）感谢阅读A）单向链表和双向链表B）双向链表和循环链表）单向链表和循环链表D）单向链表、双向链表和循环链表．线性表是具有n个(B)的有限序列。A）数据项B）数据元素C）表元素）字符n的线性表采用链式存储i个元素的算谢谢阅读法时间复杂度为(B)A）B）O(n)）2)）O(logn)感谢阅读2．在长度为n的顺序表中，若要删除第i（1≤i≤n）个元素，则感谢阅读需要向前移动的元素的次数为(B)A）iB）n-i）n-i+1n的顺序表中第精品文档放心下载为留出插入位置所需移动元素的次数为(C)A））i）n-i+1）n-i-1三、填空题．有一单链表结构如下：data…BCD…p图填空题1附图若要删除值为c的结点，应做的操作是精品文档放心下载p->link=p->link->link。．线性表L=(a,a,…a用数组存储。假定删除表中任一元素的概谢谢阅读12n率相同，则删除一个元素平均需要移动的元素个数是(n-1)/2。．设有结点定义structnode{intdata;structnode*next;且已建立如图2-2所示的带有头结点的单向链表：datahead头…^图填空题3附图函数sum的功能是：计算链表中各结点数据域之和，作为函数值返精品文档放心下载回。请填空。intsum(structnode*head)精品文档放心下载{ints=0;structnode*p;p=head->next;do{s=s+p->data;p=p->next;}while(p!=NULLreturns;}第3章栈和队列3自测习题二、选择题．有6个元素按、、4、、2、1的顺序进栈，进栈过程中可以谢谢阅读出栈，则以下可能的出栈序列是（B，）A）、、3、、、6）6、5、、、、1感谢阅读）、、4、、、5）5、6、、4、、1谢谢阅读．栈和队列都是（）A）顺序存储的线性结构）链式存储的线性结构）限制存取点的线性结构D）限制存取点的非线性结构谢谢阅读．设循环队列的队首指针用front表示，队尾指针用rear表示，感谢阅读则判断队空的条件是（A）A）front==rearB）front+1=rearC）rear+1=front谢谢阅读）rear==04、设有中缀算术表达式：15–3*（7+2）,其对应的后缀算感谢阅读术表达式为（B）A）3-72+*B）372+*-C）153*72+精品文档放心下载）3-*72+三、填空题感谢阅读性表，其操作特点是先进先出。，精品文档放心下载谢谢阅读后，现在已出栈的序列是、、5，栈顶指针是。谢谢阅读3．设有后缀算术表达式：2xy+*3y-/，其对应的中缀表达精品文档放心下载式为2*(x+y)/(3-y)。4．已知一算术表达式的中缀形式为：(a+b)-(b+c)/2，其对应的前精品文档放心下载缀表达式形式应为-+ab/+bc2。第4章串4.1自测习题一．选择题．设有一个字符串S=“ABC123XYZ”，问该串的长度为（）精品文档放心下载A）9）10C））12．设有一个字符串S=”windows”，其子串的数目是29个)精品文档放心下载A）25个）26个）27个）28个谢谢阅读．串是一种特殊的线性表，其特殊性表现在A）串中允许有空串）串可以顺序存储）串可以链式存储）数据元素是一个字符。二．填空题１．已知串S=”abaabccd”，求该串S的子串运算结果，精品文档放心下载SubStr(“abaabccd”,4,3)=感谢阅读5,0)=＿∮＿。２．两个串相等的充分必要条件是＿不仅两个串的长度相等，而感谢阅读＿且各个位置上对应的字符也要相等。３．不含任何字符的串称为＿空串＿＿，其长度为＿。感谢阅读４．只含有空格字符的串称为精品文档放心下载的个数＿。第5章数组与广义表5自测习题一．选择题１．设有二维数组A9,]，其每个元素占２个字感谢阅读节，数组按行优先顺序存储，第一个元素的存储地址为100，那感谢阅读么元素A[8,12]的存储地址为２．设有一个10谢谢阅读顺序存储，a11为第一个元素，其存储地址为1，且每个元素占1个地址空间，则a的地址为(A)75Ａ）Ｂ）17Ｃ）33Ｄ）二．填空题１．设有二维数组谢谢阅读A[6,6]精品文档放心下载的存储地址为＿＿＿＿。下标从0开始)２．设有广义表A=((x,(a,b)),((x,(a,b)),y)则广义表谢谢阅读A的长度为＿＿2＿＿，深度为＿＿4＿＿。第6章树6自测习题三.选择题如果结点A是结点B的双亲，而且结点Ｂ有４个兄弟，则结点A谢谢阅读的度是(D)A）234）5设有一棵二叉树，其１度结点有m个，２度结点有n个，则该二谢谢阅读叉树的结点总数为A）m+n）））m+2*n+1感谢阅读设有一棵二叉树，其先序遍历序列是：ABCDEFG，中序遍历序列谢谢阅读是：CBDAFEG，则该二叉树的后序遍历序列是(A)感谢阅读A）CDBFGEAB）CDFGBEAC）CDBAFGED）CDBFEGA设有13个值，由它们组成一棵哈夫曼树，则该哈夫曼树中结点感谢阅读个数共有(D)。A）B））25设电文中出现的字母为A、B、、D和E，每个字母在电文中出精品文档放心下载现的次数分别为：，23，，5和12，按哈夫曼编码，则字母C谢谢阅读的编码应是(C)(D)已知一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序列为感谢阅读HFIEJGK，则该二叉树根的右子树的根是(G)A）EB）FC）G）J设结点A有左孩子结点B，右孩子结点C，则在先序遍历、中序谢谢阅读遍历、后序遍历这三种基本遍历序列中B一定是C的(A)谢谢阅读A）前驱）不相邻结点四.填空题采用二叉链式存储结构，具有n个结点的二叉树中，一共有感谢阅读2n个指针域，其中n+1个指针域为空。一棵非空的二叉树，其第i层上最多有＿2i1＿＿＿＿个结点。谢谢阅读满二叉树是一棵深度为k的且恰好有＿2k-1＿＿＿＿个结点的精品文档放心下载二叉树。i精品文档放心下载结点有左孩子，则其编号为；如该结点有右孩子，则谢谢阅读其编号为2i+1。精品文档放心下载叶子结点的个数是m，则左、右子树都非空的结点个数是＿m-1精品文档放心下载＿＿＿＿设有一棵树（如图6-5感谢阅读根结点是＿A＿；叶子结点有＿DHIJFC的孩子是＿无；Ｅ的子孙有＿＿HIJ＿＿；Ｄ的兄弟是E＿＿；Ｂ谢谢阅读C感谢阅读的子树深度是＿；这棵树的度是＿＿。图填空题6的附图现有一表达式(a+b)*c-d/e，写出该表达式的波兰式＿精品文档放心下载-*+abc/de＿＿＿，以及逆波兰式＿ab+c*de/-＿＿＿＿＿。谢谢阅读第7章图7自测习题二、选择题．对如图7-4所示的无向图G，若从顶点V1开始，按深度优先搜精品文档放心下载索法进行遍历，则可能的访问顺序为（A）V1V2V3V5V6V4V7V8图7-4选择题1的附图A）V1V2V4V8V5V6V3V7V2V3V4V5V6V7V8感谢阅读）V1V2V3V4V8V5V6V7V2V4V5V8V3V6V7谢谢阅读．对如图7-5所示的无向图G，若从顶点V1开始，按广度优先搜感谢阅读索法进行遍历，则可能的访问顺序为（）V1V2V6V3V4V5V7V8图7-5选择题2的附图A）V1V2V3V4V5V6V7V8B）V1V2V6V3V4V5V7V8感谢阅读）V1V2V6V3V4V7V8V5D）V1V2V6V3V5V4V7V8感谢阅读．在一个无向图中，所有顶点的度数之和等于所有边数的（B）精品文档放心下载A）1倍B）2倍）1/2倍）不确定三、填空题．有n个顶点的无向连通图至少有n-1条边，有n个顶点的有向精品文档放心下载强连通图至少有n条弧。．在一个有n个顶点的无向图中，要连通所有顶点，至少需要谢谢阅读条边。n=500条边，谢谢阅读则形成的邻接矩阵共有25000个元素，其中1000个非零元素。谢谢阅读4．有n个顶点的无向图的邻接矩阵是对称的，因而只需存储精品文档放心下载(n2+n)/2条边即可。．在一个有向图中，所有顶点的度数之和等于图中弧数的2倍。感谢阅读在一个有向图中，所有顶点的出度之和等于图中弧数的1倍。谢谢阅读n个顶点和e精品文档放心下载分别为n和n-1。．无向图的邻接矩阵中一行中非零元素的个数表示该行所对应的感谢阅读顶点的度，一列中非零元素的个数表示该列所对应的顶点的感谢阅读度。第8章查找三、选择题．使用折半查找，线性表必须DA）以顺序方式存储精品文档放心下载序）以链式方式存储D）以顺序方式存储，且元素已按值排好序．散列表的地址区间为0~16，散列函数为H1(K)=K%精品文档放心下载性探测法解决冲突，将关键字序列26，，72，38，，18，依精品文档放心下载次存储到散列表中（）元素59存放在散列表中的地址为(D)A）8B）9）10）11（2）查找元素，需要比较的次数为)A）2B）3）45四、填空题．采用折半查找算法在长度为12的有序表中查找一个元素时，查精品文档放心下载找成功的平均查找长度为_37/12____。，，，，精品文档放心下载找算法依次搜索4、1、3。精品文档放心下载第9章排序二、选择题．下列排序方法中，哪一种是稳定的排序方法：(B)A）选择排序B）归并排序）快速排序D）希尔排序．快速排序每次划分的效果好坏和以下何种因素有直接关系：(C)精品文档放心下载A）关键字的排列情况B）数据元素的个数）轴的相对大小）关键字值的最大值．对以下几个关键字序列进行快速排序，以第一个元素为轴，一次精品文档放心下载划分效果最好的是：(c)A），，3，，5B），，3，，5），1，2，4，5），，，，4．对以下几个关键字序列进行快速排序，以第一个元素为轴，一次感谢阅读划分效果不好的是：A），，2，，，，7B），，1，，，，2谢谢阅读），，1，，，，5），2，3，4，5，，7精品文档放心下载5．设待排序数据元素序列为[4，1，2，3]，应用一种排序方法进精品文档放心下载行递增序排序，已知两趟后的结果为[1，，3，4]，则所选用的排精品文档放心下载序方法为：(C)A）直接插入B）直接选择）冒泡（从前向后）C冒泡（从后向前）与记录的初始排列无关谢谢阅读A）希尔排序B）归并排序有关)）直接选择排序）直接插入排序．下列字符序列中，不符合堆定义的为：A）ACDGHMPQRX）