西大2017版《数据结构》网上作业及课程考试复习资料有答案

[0012]《数据结构》

第一次作业 [填空题]

1、已知栈的基本操作函数：

int InitStack(SqStack *S); //构造空栈 int StackEmpty(SqStack *S);//判断栈空 int Push(SqStack*S,ElemType e);//入栈 int Pop(SqStack *S,ElemType *e);//出栈

函数conversion实现十进制数转换为八进制数，请将函数补充完整。

void conversion(){ InitStack(S); scanf(\ while(N){

（1） ;

N=N/8; }

while( （2） ){

Pop(S,&e);

printf(\ }

}//conversion

2.设循环队列的容量为70，现经过一系列的入队和出队操作后，front为20，rear为11，则队列中元素的个数为 。

3.在一个单链表中删除p所指结点的后继结点时，应执行以下操作： q = p->next;

p->next=_ ___;

4.一个算法的效率可分为( )效率和（ ）效率。

5.数据结构被形式地定义为（D, R），其中D是（ ）的有限集合，R是D上的（ ）有限集合。

6.下面程序段的时间复杂度是（ ）。 for(i=0;i

参考答案：

1.（1）Push(S,N%8) 2. 61 3. q->next 4. 时间 空间 5. 数据元素 关系 6. m*n

[单选题]一个具有n个顶点的有向图最多有（ ）条边 A： n×(n-1)/2

B：n×(n+1)/2

C： n×(n-1) D：n2

参考答案：B

[判断题]折半查找只适用于有序表，包括有序的顺序表和链表 参考答案：错误

[判断题]用循环单链表表示的链队列中，可以不设队头指针，仅在队尾设置队尾指针。 参考答案：正确

[判断题]在单链表中，要访问某个结点，只要知道该结点的地址即可；因此，单链表是一种

（2）!StackEmpty(S)

随机存取结构。

参考答案：错误

[单选题]判断一个循环队列Q（最多n个元素）为满的条件是: A：Q->front==(Q->rear+1)%n

B：Q->rear==Q->front+1

C：Q->front==(Q->rear-1)%n

D：Q->rear==Q->front

参考答案：A

[单选题]在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是: A：p=p->next

B：p=p->next->next

C：p->next=p

D： p->next=p->next->next

参考答案：D

[单选题]在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改

指针的操作是:

A：p->next=q;q->prior=p;p->next->prior=q;q->next=q;

B：q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;

C：q->next=p->next;q->prior=p;p->next=q;p->next=q;

D： p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;

参考答案：B

[多选题]抽象数据类型的组成部分分别为: A：数据对象

B：存储结构

C：数据关系

D：基本操作

参考答案：ACD

[多选题]不具有线性结构的数据结构是： A：图 B：栈

C：广义表

D：树

参考答案：ACD [多选题]

算法分析的两个主要方面是( )

A：正确性

B：简单性

C：空间复杂度

D：时间复杂度

参考答案：CD 第二次作业

[单选题]设一棵完全二叉树有300个结点，则共有 个叶子结点 A：150 B：152 C：154 D：156

参考答案：A

[单选题]由３个结点所构成的二叉树有 种形态. A：2 B：3 C：4 D：5

参考答案：D

[单选题]设有两个串p和q，求q在p中首次出现的位置的运算称作： A：连接

B：模式匹配

C：求子串

D：求串长

参考答案：B [单选题]

栈中元素的进出原则是:

A：先进先出

B：后进先出

C：栈空则进

D：栈满则出

参考答案：B

[单选题]链表是一种采用 存储结构存储的线性表. A：顺序 B：星式 C：链式 D：网状

参考答案：C

[单选题]数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为： A：存储结构

B：顺序存储结构

C：逻辑结构

D：链式存储

参考答案：B

[判断题]链表的每个结点中都恰好包含一个指针 参考答案：错误

[判断题]如果将所有中国人按照生日来排序，则使用哈希排序算法最快 参考答案：错误 [填空题]

1.数据的存储结构可用四种基本的存储方法表示，它们分别是( ).

2.在具有n个元素的循环队列中，队满时具有 个元素.

3. 广义表A=((a),a)的表头是（ ）。

4.稀疏矩阵一般的压缩存储方法有( )和（）两种。

5.用顺序存储的方法，将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组

R[1..N]中，若结点R[i]有右孩子，则其右孩子是（ ）

6. 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是( )

7.n个顶点的连通图至少有 边。

8.已知一个有序表为（11，22，33，44，55，66，77，88，99），则折半查找55需要比较（ ）次。

9.对一棵二叉排序树按（ ）遍历，可得到结点值从小到大的排列序列。

10.一个序列中有10000个元素，若只想得到其中前10个最小元素，则最好采用（ ）方法

参考答案：

1.顺序、链式、索引、散列 2.n-1 3.(a)

4.三元组 十字链表 5.R[2i+1]

本文来源：https://www.bwwdw.com/article/gahv.html