数据结构第一次作业

1、1 判断题(V) 1.数据的逻辑结构与数据元素本身的内容和形式无关。(X) 2.线性表的逻辑顺序与物理顺序总是一致的。(V)3. 若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。(X)4. 对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索 树都是相同的。(V) 5. 最优二叉搜索树的任何子树都是最优二叉搜索树。(V) 6. 在二叉搜索树上插入新结点时，不必移动其它结点，仅需改动某个结点的指针，使它 由空变为非空即可。(V) 7.有n (n> 1)个顶点的有向强连通图最少有n条边。X)8. 连通

2、分量是无向图中的极小连通子图。X)9. 二叉树中任何一个结点的度都是 2。X)10. 单链表从任何一个结点出发，都能访问到所有结点。二、单选题B )个1 向一个有 127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动(元素。A 8 B. 63.5 C. 63 D. 72 设有一个二维数组 Amn ，假设 A00 存放位置在 644(10)，A22 存放位置在 676(10)，每 个元素占一个空间，则 A33 在( A )位置， (10)表明用 10进数表示。A692( 10)B. 626(10)C. 709(10)D. 724( 10)3 N个顶点的连通图至少有(A)条边。A N

3、1B. NC. N1D. 04 下面程序的时间复杂度为(C)。for(int i=0; i<m;i+)for(int j=0; j<n;j+)aij=i*j;2A O(m2)B. O(n22)C. O(m*n)D. O(m+n)5 设单链表中结点的结构为(data,link)。已知指针q所指结点是指针p所指结点的直接前驱,若在*q与*p之间插入结点*s,则应执行下列哪一个操作( B )。A s->link=p->link; p->link =s; B. q->link=s; s->link =p;C. p->link=s->link; s-

4、>link =q; D. p->link=s; s->link =q;6 栈的插入和删除操作在( A )进行。A 栈顶 B.栈底 C. 任意位置D.指定位置7 若让元素 1 ，2， 3依次进栈，则出栈次序不可能出现哪种情况(C )。A 3，2，1B. 2，1，3 C. 3，1，2 D. 1，3，28 广义表 A(a), 则表尾为( C )。A aB. () C.空表D.( a)9 采用邻接表存储的图的深度优先遍历算法类似于二叉树的( B )。A 中序遍历 B. 前序遍历 C. 后序遍历 D. 按层次遍历10 每次从无序表中挑选出一个最小或最大元素， 把它交换到有序表的一端，

5、此种排序方法叫做 ( B )排序。A 插入 B. 选择 C. 交换 D. 外排序三、填空题1. 算法是一个有穷的指令集， 它为解决某一特定任务规定了一个运算序列。 它应具有输入、输 出、 确定性 、有穷性和可执行性等特性。2. 当问题的规模n趋向无穷大时，算法执行时间 T(n)的数量级被称为算法的时间复杂度_。3. 在一棵度为 3的树中，度为 2的结点个数是 1，度为 0的结点个数是 6，则度为 3的结点个数是2 。4. 当用长度为n的数组顺序存储一个栈时，若用 top=n表示栈空，则表示栈满的条件为top=0 。5. 对序列 (49,38,65,97,76,27,13,50) 采用快速排序法

6、进行排序，以序列的第一个元素为基准元素得到的划分结果是 13 27 384550 65 76 97 。6. 对于一棵具有n个结点的树，该树中所有结点的度数之和为 n-1。7. 请指出在顺序表 5、11、23、35、51、64、72、85、88、90、98中，用折半查找关键码 30需做 5次关键码比较。8. 若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100, 则第12个元素的存储地址是 1 44 。9. 在一个长度为n的顺序表中，向第i个元素(K i < n +1)之前插入一个新元素时，需要向后移动 _n-i+1 个元素。10. 设有两个串p和q,求q在p中

7、首次出现的位置的运算称作 模式匹配_。四、程序阅读填空1. 在顺序表中第 i 个位置插入新元素 xtemplate <class Type> int SeqList<Type>:Insert (Type & x, int i)if (i<0|i>last+1|last=MaxSize-1) return 0; /插入不成功else last+;for( _int j=last;j>i;j-)dataj=dataj-1datai = x;return 1;/插入成功2. 直接选择排序的算法template <class Typevoid S

8、electSort(datalist<Type> & list) for(inti=0; i<list.CurrentSize-1;i+) SelectExchange(list,i);template <class Type> viod SelectExcha nge(datalist<Type> & list, const int i)int k = i;for(int j=i+1;j< list.CurrentSize;j+)if(list.Vectorj.getKey()<list.Vectork.getKey()k

9、=j;/ 当前具有最小关键码的对象if(k!=i) Swap(list.Vectori, list.Vectork); /交换五、简答题1. 线性表可用顺序表或是链表存储，此两种存储表示各有哪些优缺点？答：顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或（按下标）直 接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会 发生改变，因此，不以扩充。同时，由于在插入或删除时，为保持原有次序（没有规定元素进 栈顺序），平均需要移动一半（或近一半）元素，修改效率不高。连接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间,就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需 要保持原来的逻辑顺序，因此不必移动数据，只需