一、选择题（共15题，每题2分，共计30分）1、单链表的一个存储结点包含（ C ）A.指针域和链域B.指针域或链域C.数据域或指针域D.数据域和链域2、采用线性链表表示一个向量时，要求占用的存储空间地址（ D ）。

A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、可连续可不连续3、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（ B ）。

A. n-2B. n-1C. nD. n+14、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。

A、s→next = p→next; p→next = s;B、p→next = s; s→next k = q;C、p→next = s→next; s→next = p;D、q→next = s; s→next = p;5、在数组A中，每一个数组元素A[i, j] 占用3个存储字，行下标i从1到8，列下标j 从1到10。

所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（ C ）。

A、 80B、 100C、 240D、 2706、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。

A、栈B、队列C、循环队列D、优先队列7、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。

A、4, 3, 2, 1B、2, 4, 3, 1C、1, 2, 3, 4D、3, 2, 1, 48.下述各类表中可以随机访问的是（D ）。

A. 单向链表B. 双向链表C.单向循环链表D.顺序表9.在一个长度为n的顺序表中为了删除第5个元素，从前到后依次移动了15个元素。

则原顺序表的长度为（ B ）。

A. 21B. 20C. 19D. 2510.元素1，3，5按顺序依次进栈，则该栈的不可能的输出序列是（ B ）。

A. 5 3 1B. 5 1 3C. 3 1 5D. 1 5 311.一个队列的入队序列是5，6，7，8，则队列的输出序列是（ A ）。

A. 5 6 7 8B. 8 7 6 5C. 7 8 6 5D.可能有多种情况12．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（C ）。

A．p=q->next B．p->next=q C．p->next=q->next D．q->next=NULL13.设一棵哈夫曼树共有n个非叶结点，则该树一共有（ B ）个结点。

A. 2*n-1B. 2*n +1C. 2*nD. 2*(n-1)14.对如图1所示二叉树进行中序遍历，结果是（ A ）。

A. dfebagcB. defbagcC. defbacgD.dbaefcg15 . 一组记录的关键字序列为（37，70，47，29，31，85），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（ D ）。

A ．31，29，37，85，47，70B ．29，31，37，47，70，85C ．31，29，37，70，47，85D ．31，29，37，47，70，85 一、选择题（共15题，每题2分，共计30分）1. 一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。

A 、4, 3, 2, 1B 、2, 4, 3, 1C 、1, 2, 3, 4D 、3, 2, 1, 4 2.下述各类表中可以随机访问的是（ D ）。

A. 单向链表B. 双向链表C.单向循环链表D.顺序表3.在一个长度为n 的顺序表中为了删除第5个元素，从前到后依次移动了15个元素。

则原顺序表的长度为（B ）。

A. 21B. 20C. 19D. 254.元素2，4，6按顺序依次进栈，则该栈的不可能的输出序列是（ B ）。

A. 6 4 2B. 6 2 4C. 4 2 6D. 2 6 4 5.一个队列的入队序列是5，6，7，8，则队列的输出序列是（A ）。

A. 5 6 7 8B. 8 7 6 5C. 7 8 6 5D.可能有多种情况 6、在数组A 中，每一个数组元素A[i, j] 占用3个存储字，行下标i 从1到8，列下标j 从1到10。

所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（ C ）。

A 、 80B 、 100C 、 240D 、 2707、在一个单链表中，p 、q 分别指向表中两个相邻的结点，且q 所指结点是p 所指结点的直接后继，现要删除q 所指结点，可用语句（ C ）。

A ．p=q->next B ．p->next=q C ．p->next=q->next D ．q->next=NULL 8、数据结构中，与所使用的计算机无关的是数据的（A ）结构。

A. 逻辑B. 物理C. 存储D. 逻辑与物理 9.设一棵哈夫曼树共有n 个非叶结点，则该树一共有（ B ）个结点。

A. 2*n-1B. 2*n +1C. 2*nD. 2*(n-1) 10．与中缀表达式a+b*c-d 等价的前缀表达式是_c__。

A.+a-*bcdB.*+-abcdC.-+a*bcdD.abcd+*-11．带头结点的单向链表为空的判断条件是（D ）（设头指针为head ）。

图1 c b c d e f g aA ．head = =NULLB ．head!=NULLC ．head->next= =headD ．head->next= =NULL 12．链表所具备的特点是（ C ）。

A ．可以随机访问任一结点B ．占用连续的存储空间C ．插入删除元素的操作不需要移动元素结点D ．可以通过下标对链表进行直接访问 13．设有一个长度为n 的顺序表，要在第i 个元素之前插入一个元素（也就是插入元素作为新表的第i 个元素），则移动元素个数为（ A ）。

A ．n-i+1 B ．n-i C ．n-i-1 D ．i 14．下列算法suanfa2的时间复杂度为__c__。

int suanfa2(int n) { int t=1； while(t<=n) t=t*2； return t ； }A ．O(n)B ．O(n 2) C ．O(log2n) D ．O(1) 15.广义表(a,(b),c,(d,(e)))的表尾是_D___。

A.(d,(e))B.(d,(e))）C.(b),c,(d,(e))D.((b),c,(d,(e)))二、填空题（每空1分，共13分）1. 树中结点A 的 ________分支数____________ 称为结点A 的度。

2. 一棵深度为4的二叉树最多有 ___15____ 个结点。

3. 具有10个顶点的无向图,边的总数最多为 _____45________ 。

4．结构中的数据元素存在 一对多 的关系称为树形结构。

6．如图1所示的二叉树，其先序遍历序列为___abdefcg______。

7．如图1所示的二叉树，其后序遍历序列为___fedbagc______。

8．如图2所示的二叉树，其前序遍历序列为___abdefcg______。

g fab d ec9．n 个元素进行冒泡法排序，通常需要进行___n-1_____趟冒泡，第j 趟冒泡要进行_n-j_____次元素间的比较。

10．哈希函数是记录 数据元素 与该记录存储地址之间所构造的对应关系。

二、填空题（每空1分，共15分）1．1.把数据存储到计算机中,并具体体现数据之间的逻辑结构称为__存储结构____ __。

2.在一棵树中____根__结点没有前驱结点，_叶子__结点没有后继结点。

3. n 个元素进行冒泡法排序，通常需要进行__n-1______趟冒泡，第j 趟冒泡要进行__n-j____次元素间的比较。

4．一棵深度为6的满二叉树有__31____个非终端结点。

5．结构中的数据元素存在 一对多 的关系称为树形结构。

2． 6．在一个单向链表中p 所指结点之后插入一个s 所指向的结点时，应执行s->next=p->next;和 p->next=s 的操作。

7．队列的插入操作在 队尾 进行，删除操作在 队头 进行。

8．在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是_左孩子指针_ 、 数据、 右孩子指针 。

3． 9．中序遍历二叉排序树可得到一个 递增有序序列 。

4． 10．如图所示的二叉树，其中序遍历序列为___dgbaechif_____ _。

三、阅读理解题 （第1题4分，第2，3题各3分，共计10分）1．给出下列递归过程的执行结果。

(1) void unknown ( int w ) {if ( w ) {unknown ( w-1 );for ( int i = 1; i <= w; i++ ) printf (“%d ”, w);printf (“\n ”); } }调用语句为 unknown (4). 执行结果为： 1 2 23 3 34 4 4 4ef gi b a c h d(2) void unknown ( int m ) {printf (“%d ”, n % 10) ;if ( int ( n / 10 ) ) unknown ( int ( n / 10 ) ); }调用语句为unknown ( 582 )。

执行结果为：2852．以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。

void Inorder (struct BTreeNode *BT){ if(BT!=NULL){① Inorder(BT->left);② printf(“%c”,BT->data);③ Inorder(BT->right);}}3. 以下程序是后序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中，左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。

void Postorder (struct BTreeNode *BT){ if(BT!=NULL){① postorder(BT->left);② postorder(BT->right);③ printf(“%c”,BT->data);}3．设有序顺序表为 { 10, 20, 30, 40, 50, 60, 70 }，采用折半搜索时，搜索成功的平均搜索长度是多少？17/7四、简答题（每题4分，共16分）(1) 在一个有n个元素的顺序表的第i个元素（1 ≤ i ≤ n）之前插入一个新元素时，需要向后移动多少个元素？n- i + 1(2) 当一个栈的进栈序列为1234567时，可能的出栈序列有多少种？6457321是否是合理的出栈序列？不合理(3) 数据结构的逻辑结构和存储结构由哪些具体结构组成？逻辑结构：线性结构，树型结构，图形结构，集合存储结构：顺序存储，链式存储，散列存储，索引存储(4) 试述线性结构中顺序存储和链式存储的优缺点？顺序存储：存储实现简单，读取数据方便，插入删除数据复杂度高，存储空间冗余大链式存储：存储实现稍复杂，读取数据必须从头开始，插入删除数据复杂度低，存储空间冗余小。