1数据结构课程研究的主要内容包括（）（）（）2一个完整的算法应该具有_____ _____ ______ ______ ______五个特性3数据的逻辑结构可分为_____ ______两大类4数据的逻辑结构是指而存储结构是指5逻辑上相邻的数据元素在物理位置上也相邻是存储结构的特点之一6为了实现随机访问线性结构应该采用存储结构7链式存储结构的主要特点是8算法分析主要从和这两个方面对算法进行分析（1）数据（2）数据元素（3）数据类型（4）数据结构（5）逻辑结构（6）存储结构（7）线性结构（8）非线性结构第二章作业一、判断题(在你认为正确的题后的括号中打√，否则打X)。

1．线性表的逻辑顺序与存储顺序总是一致的。

2．顺序存储的线性表可以按序号随机存取。

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

7．线性表的链式存储结构优于顺序存储结构。

8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。

9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

二、单项选择题。

1．线性表是( ) 。

(A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空；(C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。

2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。

插入一个元素时平均要移动表中的（）个元素。

(A) n/2 (B) n+1/2 (C) n -1/2 (D) n 3．线性表采用链式存储时，其地址( ) 。

(A) 必须是连续的； (B) 部分地址必须是连续的；(C) 一定是不连续的； (D) 连续与否均可以。

4．用链表表示线性表的优点是（）。

(A)便于随机存取(B)花费的存储空间较顺序存储少(C)便于插入和删除(D)数据元素的物理顺序与逻辑顺序相同5．下面关于线性表的叙述错误的是( )。

() 线性表采用顺序存储，必须占用一片地址连续的单元；() 线性表采用顺序存储，便于进行插入和删除操作；() 线性表采用链式存储，不必占用一片地址连续的单元；() 线性表采用链式存储，便于进行插入和删除操作；6.设存储分配是从低地址到高地址进行的。

若每个元素占用4个存储单元，则某元素的地址是指它所占用的单元的( )。

A．第1个单元的地址 B．第2个单元的地址C．第3个单元的地址 n第4个单元的地址7.若线性表采用顺序存储结构，每个元素占用4个存储单元，第1个元素的存储地址为100，则第12个元素的存储地址是( )。

A．112 B．144 C．148 0．4128.若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值应该是( )。

A．i>O B．i≤n C．1≤i≤n D．1≤i≤n+19.若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，i的合法值应该是( )。

A．i>O B．i≤n C．1≤i≤n D。

1≤i≤n十110.若长度为n的非空线性表采用顺序存储结构，删除表的第i个数据元素，首先需要移动表中( )个数据元素。

A．n-i B．n+i C．n-i+l D．n-i-111.若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，需要移动表中( )个元素。

A．i B．n+i C．n-i+l D．n-i-112.设单链表中结点的结构为typedef struct node { //链表结点定义ElemType data; //数据struct node * Link; //结点后继指针} ListNode;已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作（）A. s->link = p; p->link = s;B. s->link = p->link; p->link = s;C. s->link = p->link; p = s;D. p->link = s; s->link = p;第三章作业1．栈和队列都是（）A．限制存取位置的线性结构B．顺序存储的线性结构C．链式存储的线性结构D．限制存取位置的非线性结构2．若数组s[0..n-1]为两个栈s1和s2的共用存储空间，且仅当s[0..n-1]全满时，各栈才不能进行进栈操作，则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为（）A．：0和n-1B．1和n/2 C．－1和nD．－1和n+13.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为( )A.4B.5C.6D.74．如图所示，设输入元素的顺序是A，B，C，D，通过栈的变换，在输出端可得到各种排列。

若输出序列的第一个元素为D，则输出序列为_ ____________。

5．队列中允许进行删除的一端为___ ______。

6.假设以S和X分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为___ __。

第五章数组和广义表单项选择题。

(1)空的广义表是指广义表（）。

A．深度为0 B．尚未赋值C．不含任何原子元素D．不含任何元素(2)广义表中元素分为（）。

A．原子元素B．表元素C．原子元素和表元素D．任意元素(3)广义表的长度是指（）。

A．广义表中元素的个数B．广义表中原子元素的个数C．广义表中表元素的个数D．广义表中括号嵌套的层数(4)广义表的深度是指（）。

A．广义表中元素的个数B．广义表中原子元素的个数C．广义表中表元素的个数D．广义表中括号嵌套的层数(5)在一个长度为n，包含m个原子元素的广义表中，（）。

A．m和n相等B．m不大于n C．m不小于n D．m与n无关(6)广义表A=(( )，(a)，(b，(c，d)))的长度为（）。

A．2 B．3 C．4 D．5(7)广义表A：(( )，(a)，(b，(c，d)))的深度为（）。

A．2 B．3 C．4 D．5(8)设有一5阶上三角矩阵A［1..5，1..5］，现将其上三角中的元素按列优先顺序存放在一堆数组B［1..15］中。

已知B［1］的地址为100，每个元素占用2个存储单元，则A［3，4］的地址为（）A．116 B．118 C．120 D．122第六章树和二叉树一、判断题(在你认为正确的题后的括号中打√，否则打X)。

(1)在树型结构中，每一个结点最多只有一个前驱结点，但可以有多个后继结点。

( )(2)在树型结构中，每—个结点不能没有前驱结点。

( )(3)在度为k的树中，至少有一个度为k的结点。

( )(4)度为2的树是二叉树。

( )(5)在非空完全二叉树中，只有最下面一层的结点为叶结点。

( )(6)在完全二叉树中，没有左孩子的结点一定是叶结点。

( )(7)在完全二叉树中，没有右孩子的结点一定是叶结点。

( )(8)在结点数目一定的前提下，各种形态的二叉树中，完全二叉树具有最小深度。

(9)满二叉树中的每个结点的度不是0就是2。

( )(10)在所有深度相同的二叉树中，满二叉树具有最大结点数目。

( )(11)由二叉树的前序序列和中序序列可以唯一地确定一棵二叉树。

( )(12)由二叉树的中序序列和后序序列可以唯一地确定一棵二叉树。

( )(13)由二叉树的前序序列和后序序列可以唯一地确定一棵二叉树。

( )(14)哈夫曼树中不存在度为1的结点。

( )(15)满二叉树一定是完全二叉树。

( )二、单项选择题。

(1)树型结构最适合用来描述( )。

A．有序的数据元素B．无序的数据元素C．数据元素之间具有层次关系的数据D．数据元素之间没有关系的数据(2)按照二叉树的定义，具有3个结点的二叉树有( )种形态(不考虑数据信息的组合情况)。

A．2 B．3 C．4 D．5(3)若一棵二叉树有10个度为2的结点，则该二叉树的叶结点的个数是( )。

A．9 B．11 C．12 D．不确定(4)若一棵满二叉树有2047个结点，则该二叉树中叶结点的个数为( )。

A．512 B．1024 C．2048 D．4096(5)深度为h的满二叉树的第i层有( )个结点。

(i≤h) ( )A．2i—1 B．2i-1C．2h—1 D．2h-1(6)深度为h的满二叉树共有( )个结点。

(i<h)A．22h-1B．22h-1 C．2h-1 D．2h-1(7)若某完全二叉树的深度为h，则该完全二叉树中至少有( )个结点。

A．2h B．2h-1 c．2h+1 D．2h—1三、填空题。

(1)任何非空树中有且仅有一个结点没有前驱结点，该结点就是树的______ ______。

(2)树的层次定义为____________________。

(3)度为k的树中第i层最多有______________个结点(i≥1)。

(4)深度为h的k叉树最多有_______ _____________个结点。

(5)非空二叉树一共有_______________种基本形态。

(6)非空二叉树中第i层最多有______________个结点。

(7)深度为h的二叉树最多有_____________________________个结点。

(8)具有n个结点的完全二叉树的深度h=____________________。

(9)若二叉树有N0个叶结点，n2个度为2的结点，则N0与n2的关系是________ ______。

(10)若具有n个结点的非空二叉树．树有N0个叶结点，则该二叉树有_______ _____个度为2的结点，___________个度为1的结点。

(11)对具有n个结点的完全二叉树按照层次从上到下，每一层从左到右的次序对所有结点进行编号，编号为i的结点的双亲结点的编号为______________，左孩子的编号为_______________，右孩子的编号为______________。

(12)若具有n个结点的二叉树采用二叉链表存储结构，则该链表中有_____________个指针域，其中有________________个指针域用于链接孩子结点，______________个指针域空闲存放着NULL。

(13)已知二叉树的前序遍历序列为ABDCEFG，中序遍历序列为DBCAFEG，其后序遍历序列为__________。