软工期末数据结构复习习题

1数据结构练习题数据结构练习题（15 章）一、选择题1、从逻辑上可以把数据结构分为（ C ）两大类。A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构2、以下数据结构中，哪一个是线性结构（ D ）？ A广义表 B. 二叉树 C. 稀疏矩阵 D. 串3、在下面的程序段中，对 x 的赋值语句的频度为（ C ）for (i=1;inext=s;s-next=p-next; B s-next=p-next;p-next=s;Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s;10、对于一个头指针为 head 的带头结点的单链表，判定该表为空表的条件是（ B ）Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL11、 一个栈的输入序列为 123n，若输出序列的第一个元素是 n，输出第 i（1(空格串是由空格组成的)C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储17、设有两个串 p 和 q，其中 q 是 p 的子串，求 q 在 p 中首次出现的位置的算法称为（ C ）A求子串 B联接 C匹配 D求串长18、 设有数组 Ai,j，数组的每个元素长度为 3 字节，i 的值为 1 到 8 ，j 的值为 1 到10，数组从内存首地址 BA 开始顺序存放，当用以列为主存放时，元素 A5，8的存储首地址为( B )。30*6180A. BA+141 B. BA+180 C. BA+222 D. BA+22519、已知广义表 L=（x,y,z） ，a， （u，t，w） ） ，从 L 表中取出原子项 t 的运算是（ D ） 。A. head（tail（tail（L） ） ） B. tail（head（head（tail（L） ） ） ） C. head（tail（head（tail（L） ） ） ） D. head（tail(head（tail（tail（L） ） ）)）20、广义表 A=(a,b,(c,d),(e,(f,g),则下面式子的值为（ D ） 。Head(Tail(Head(Tail(Tail(A)A. (g) B. (d) C. c D. d二、判断题1、 数据元素是数据的最小单位。( )2、算法可以用不同的语言描述，如果用 C 语言或 PASCAL 语言等高级语言来描述，则算法实际上就是程序了。( Y ) 3、 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )4、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( )5、线性表的特点是每个元素都有一个前驱和一个后继。( )6、一个稀疏矩阵 Am*n采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换，并把 m 和 n 的值互换，则就完成了 Am*n的转置运算。（ ） 7、所谓取广义表的表尾就是返回广义表中最后一个元素。 （ ）三、填空题1、数据的物理结构包括 数据元素 的表示和 关系 的表示。2、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_顺序_存储结构。3、线性表 L=（a1,a2,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_(n-1)/2_。4、对于一个具有 n 个结点的单链表，在已知的结点*p 后插入一个新结点的时间复杂度为_O(1)_,在给定值为 x 的结点后插入一个新结点的时间复杂度为_ O(n)_。35、带头结点的双循环链表 L 中只有一个元素结点的条件是：_L-next-next=L _6、一个栈的输入序列是：1，2，3 则不可能的栈输出序列是_3 1 2_。7、用 S 表示入栈操作，X 表示出栈操作，若元素入栈的顺序为 1234，为了得到 1342 出栈顺序，相应的 S 和 X 的操作串为_ SXSSXSXX_。8、_队列_又称作先进先出表。9、组成串的数据元素只能是_字符_。 10、设有 C 语言描述的二维数组 A1020,其每个元素占两个字节，第一个元素的存储地址为 100，若按行优先顺序存储，则元素 A66存储地址为_352_。(没说明，则下标从0 开始) 四、算法与应用题1. 设线性表存放在向量 Aarrsize的前 elenum 个分量中且递增有序，试写一算法将 x 插入到线性表的适当位置，以保持线性表的有序性并分析其时间复杂度。#define arrsize 100bool sortinsert(Elemtype A,int elenum , Elemtype x)int i;if(elenum = = arrsize)printf(“该数组向量已满”)； return false;i=elenum-1;while(Aix i- -;Ai+1=x;return true;/ 2.已知带头结点的动态单链表 L 中的结点是按整数值递增排列的，试写一算法将值 x 为的结点插入到表 L 中，使 L 仍然有序。/线性表的单链表存储结构typedef struct Lnode ElemType data;struct Lnode *next; LNode , *LinkList;LinkList sortinsert(LinkList L,int x) /* 带头结点*/ LinkList p,q, s;4s=(LinkList)malloc(sizeof(LNode);if(!s) printf(“动态空间分配不成功”)； exit(-1);s-data=x;q=L;p=L-next; while ( p!=NULL s-next=q-next; q-next=s ; return L; 3.在长度大于 1 的单循环链表 L 中，既无头结点也无头指针。s 为指向链表中某个结点的指针，试编写算法删除结点*s 的直接前趋结点。/条件是长度大于一#include using namespace std;typedef struct Lnode ElemType data;struct Lnode *next; LNode , *LinkList;bool delete_prior(LinkList s)LinkList p;LinkList q;q=s;p=s-next;while(p-next!=s) q=p; p=p-next;q-next =s;delete p;五、程序填空题1、 下面是用 c 语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用 L 返回逆置后的链表的头指针，试在空缺处填入适当的语句。5void reverse（linklist q-next=p；p=q；(2) q=L _ ; (3) L=p； 2、对单链表中元素按插入方法排序的 C 语言描述算法如下，其中 L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。 （10 分）typedef struct nodeint data; struct node *next;linknode,*link;void Insertsort(link L) link p,q,r,u;p=L-next; (1) L-next=NULL _;while(2)_ p!=NULL _) r=L; q=L-next;while(3) q!=NUll _q=q-next;u=p-next; (4)_ p-next=q _ ; (5)_ r-next= p_; p=u;第六章练习选择题1. 设树 T 的度为 4，其中度为 1，2，3 和 4 的结点个数分别为 4，2，1，1 则 T 中的叶子数为（ D ）A5 B6 C7 D82. 设森林 F 对应的二叉树为 B，它有 m 个结点，B 的根为 p,p 的右子树结点个数为 n,森林F 中第一棵树的结点个数是（ A ）Am-n Bm-n-1 Cn+1 D条件不足，无法确定3若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是（B ）A9 B11 C15 D不确定4具有 10 个叶结点的二叉树中有（ B ）个度为 2 的结点， 6A8 B9 C10 Dll5一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是（ E ）A 250 B 500 C254 D505 E以上答案都不对 6. 有 n 个叶子的哈夫曼树的结点总数为（ D ） 。A不确定 B2n C2n+1 D2n-17. 一棵具有 n 个结点的完全二叉树的树高度（深度）是（ A ）Alogn+1 Blogn+1 Clogn Dlogn-18深度为 h 的满 m 叉树的第 k 层有（ A）个结点。(1=1) 4度为二的树就是二叉树。5. 在中序线索二叉树中，每一非空的线索均指向其祖先结点。填空题：1如某二叉树有 20 个叶子结点，有 30 个结点仅有一个孩子，则该二叉树的总结点数为_69_。2具有 256 个结点的完全二叉树的深度为_9_。3已知一棵度为 3 的树有 2 个度为 1 的结点，3 个度为 2 的结点，4 个度为 3 的结点，则该树有_12_个叶子结点。4在一棵二叉树中，度为零的结点的个数为 N0,度为 2 的结点的个数为 N2,则有 N0 =_ N2 _+ 1_5已知二叉树有 50 个叶子结点，则该二叉树的总结点数至少是_99_。6一个有 2001 个结点的完全二叉树的高度为_11_。7设 F 是由 T1,T2,T3 三棵树组成的森林,与 F 对应的二叉树为 B,已知 T1,T2,T3 的结点数分别为 n1,n2 和 n3 则二叉树 B 的左子树中有_n1-1_个结点，右子树中有_n2+n3_个结点。作业题1、给定一组权值 2,3,5,7,11,13,17,19,23,29，31，37，41，（1）试画出用 Huffman 算法建造的 Huffman 树；（2）求平均编码长度（）考虑概率解：（1）82381439565 7834 3117 1710 75 52 337 4153 4224 2919 2311 13（2） （7（23）6557 4（176613）3（313741291923） ）/ 2382、 设一棵二叉树的先序、中序遍历序列分别为先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C（1）画出这棵二叉树。（2）画出这棵二叉树的后序线索树。解：（1）AB CD EG HF(2)后序遍历为：F D B G H E C A9AB CD EG HF3二叉树存储结构同上题，以下程序为求二叉树深度的递归算法，请填空完善之。int depth(bitree bt) /*bt 为根结点的指针*/int hl,hr;if (bt=NULL) return(1)_ 0_);hl=depth(bt-lchild); hr=depth(bt-rchild);if(2) hlhr _) (3)_ hr=hl_；return(hr+1); 4线索二叉树有数据域 data，左右孩子域 lchild 和 rchild，左右标志 ltag 及 rtag，规定标志为 1 对应的孩子域是线索，0 则为指向孩子的指针。规定在储存线索二叉树时，完成下面中序线索化过程。 （存储线索二叉树，不增加头结点，只在原有的由 tree 指向的二叉树中增加线索，此处也不考虑 c 语言的具体语法与约定，线索化前所有的标志 tag 都是 0） 。/* pre 是同 tree 类型相同的指针，初值是 null */thread_inorder (tree) if(tree!=null) thread_inorder(1) tree-lchild _);if(tree-lchild=(2)_ NULL_) tree-ltag=1; tree-lchild=pre; if(3) tree-rchild_ = null) (4) tree-rtag=1_; (5) tree-rchild=tree _;pre=p; thread-inorder(6)_ tree-rchild _); 5、已知一棵满二叉树的结点个数为 20 到 40 之间的素数，此二叉树的叶子结点有多少个？（请给出具体的推理过程）解： 166、一棵共有 n 个结点的树，其中所有分支结点的度均为 K，求该树中叶子结点的个数。kn1)(07. 假设一个二叉树的两种遍历如下：前序：ABFGCHDEIJLK 中序：FGBHCDILJKEA10画出这棵二叉树以及它的中序线索树；解：ABF CLJHG DIEKABF CLJHG DIEK第七章练习选择题1设无向图的顶点个数为 n，则该图最多有（ B ）条边。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En 22一个 n 个顶点的连通无向图，其边的个数至少为（ A ）。An-1 Bn Cn+1 Dnlogn；3一个有 n 个结点的图，最少有（ B ）个连通分量，最多有（ D ）个连通分量。A0 B1 Cn-1 Dn4在一个无向图中，所有顶点的度数之和等于所有边数（ B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C ）倍。A1/2 B2 C1 D45下列哪一种图的邻接矩阵是对称矩阵？（ B ）A有向图 B无向图 CAOV 网 DAOE 网6当一个有 N 个顶