数据结构题目

Question

一、选择题(每题2分)
1.数据的不可分割的基本单位是 __。
A.元素 B.结点 C.数据类型 D.数据项
2.____是线性表。
A.(孔子,诸葛亮,曹雪芹) B.{A,B,C,D}
C.{10,11,12,13,14} D.(1,2,3,...)
4.将线性表的数据元素以____结构存放, 查找一个数据元素所需
的时间不依赖于表的长度。
A.循环双链表 B.哈希(Hash)表 C.一维数组 D.单链表
5.设数组A[1..8,1..10]的基地址为4000, 每个元素占2个存储单元,若以列序为主序顺序存储,则元素A[4,7]的存储地址是____。(假定无第0行第0列元素)
A.4072 B.4104 C.4102 D.4074
6.设依次进入一个栈的元素序列为c,a,b,d,不可得到出栈的元素序列有_____。
A.a.b,c,d B.a,d,c,b C.b,a,d,c D.c,d,a,b

二、填空(每空1分)
1.一个数据结构在计算机中的表示(映象)称为 ________________。
2.线性表中 ____________________________ 称为表的长度。
3.栈中元素的进出原则为 _____________________ 。
4.设数组A[1..10,1..8]的基地址为2000,每个元素占2个存储单元,若以行序为主序顺序存储,则元素A[4,5]的存储地址为_____；若以列序为主序顺序存储,则元素A[4,5]的存储地址为______。
5.一个算法具有5个特性:__________________、__________________、________________、有零个或多个输入、有一个或多个输出。
6.设长度为n的线性表顺序存贮,若在它的第i-1和第i个元素之间插入一个元素, 共需移动 _________ 个元素

三、回答下列问题 (每小题5分)
1.线性表的存储结构,在什么情况下采用顺序结构? 为什么?
2.线性表的存储结构,在什么情况下采用链接表(如:单链表)结构?为什么?

四、试画出下列存储结构图(每小题4分)
1.数组A[1..2,0..2] 的以列序为主序的顺序存储结构。
2.依次将元素 A,C,D,B 插入一个初始状态为空的链式栈中,试画出所有插入完成之后的链式栈。

五、算法设计(算法中必须有注释,每小题8分)
1. 已知队列 Q 以循环队列存储。写出 Q 的存储结构类型描述，并试编写算法实现将元素 x 插入队列 Q 的入队操作 EnQueue(Q,x)和从队列 Q 中获取队首元素的函数 GetTop(Q)。

2. 假设线性表 L=(a1,a2,……,an) 用带头结点的单链表存储表示，试编写算法对其实现就地逆置，即利用原链表中每一个结点存储空间，使得元素的逻辑次序改变为(an,……, a2,a1)。
3.设n个元素的线性表顺序存储在一维数组 st[1..maxlen] 的前n个位置上,试写出算法:删除表中第i(1≤i≤n)个元素。

Answer 1

一、1、最小单位应该是“位”，数据类型根本就不是一个单位

2、A

4、B

5、4108

6、A

二、1、物理结构

2、数据元素的个数

3、后进先出

4、2056、2086

5、有穷性、确定性、可行性

6、n－i＋1

Answer 2

一、
1. A
2. D
4. B

二、
1.一个数据结构在计算机中的表示(映象)称为 __数据的物理（存储）结构__。

2.线性表中 ___结点的个数n___ 称为表的长度。

3.栈中元素的进出原则为 __后进先出__ 。

5.一个算法具有5个特性:___有穷性___、__确定性__、__可行性__、有零个或多个输入、有一个或多个输出。

Answer 3

时间问题，明天把五题补上，或者发到你邮箱里

一，

1 D 数据元素是数据的基本单位, 数据项是不可分割的最小单位。

2 C 线性表是由类型相同的数据元素组成的有限序列。线性表的数据元素可以是最简的数值和字符，也可以是比较复杂的信息。

4 B 根据设定的哈希函数和处理冲突的方法将一组关键字映像到一个有限的连续的地址集上，并以关键字在地址集中的“象”作为记录在表中的存 储位置，这种表便成为哈希表。哈希函数是一个映像，因此哈希函数的设定很灵活，不需进行比较就可以直接取得所查记录。

5 C 根据二维数组A[u1][u2]的列优先映射所对应的映射函数 map(i1，i2) = i2 * u1 + i1 其中u1=8 u2=10 ; i1=3 i2=6 ; map=6*8+3=51
即4000+51*2=4102

6 D 根据后进先出原则c/d/a/b：c进栈然后出栈；a,b,d先后进栈，d出栈；此时栈中有a,b两个元素，必须是b先出栈，所以不会出现c/d/a/b序列

二，1 数据的存储结构（即物理结构） 2、线性表中数据元素的个数n称为线性表的长度。 3 后进先出

4、2056；2086。。u1=10，u2=8；i1=4-1=3，i2=5-1=4 ；行优先：map(i1，i2) = i1 * u2 + i2=28；列优先：map(i1，i2) = i2 * u1 + i1 =43

5 一个算法应该具有以下特点： 有穷性 、确定性、有零个或多个输入、有一个或多个输出、有效性 6、 n-i+1

三，1、当要求随机存取线性表的任一元素，且逻辑上相邻的元素在物理位置上也相邻时，要采用顺序结构。

因为线性表的顺序存储结构是用一组地址连续的存储单元依次存储线性表的元素，

用元素在存储器中的“物理位置相邻”表示线性表中数据元素之间的逻辑关系，可随机存取任一个数据元素，是一种随机存储结构。

2、当不要求逻辑上相邻的元素在物理位置上也相邻，不要求随机存取任一数据元素，但需要进行有效率的插入、删除等操作时，要采用链式存储 结构。（只讨论单链式）

因为线性表的链式存储结构中用结点中的指针域表示数据元素之间的逻辑关系，这样逻辑上相邻的两个元素部要求物理存储位置也相邻。

且每个元素的存储位置由其直接前驱的指针表示，方便进行插入、删除等操作，是一种非随机存储结构。

四，1、 A[1][0] - A[2][0] - A[1][1] - A[2][1] - A[1][2] - A[2][2] （自己画框框吧。。。）

2、。。。。这个就不用了吧 你肯定会的

五 1、//--------循环队列----队列的顺序存储结构----------
#define MAXQSIZE 100 //最大队列长度
typedef struct {
QElemType *base; // 初始化的动态分配存储空间
int front; //头指针，若队列不空，指向队列头元素
int rear; //尾指针，若队列不空，指向队列尾元素的下一个位置
} Q ;

Status EnQueue (Q, x){ //插入元素x为新的队尾元素
if (( Q.rear +1)%MAXQSIZE = = Q.front ) return ERROR; // 队列满
Q.base[Q.rear] = x ;
Q.rear = (Q.rear+1)%MAXQSIZE ;
return OK ;
}

Status GetTop(Q, QElemType &e) { //若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；
if (Q.front = = Q.rear) return ERROR ; //队列为空 返回error
e = Q.base[Q.front];
Q.front = (Q.front +1 ) % MAXQSIZE ;
return OK;
}

2、一个带头结点的线性链表类型定义如下：
typedef struct LNode { // 结点类型
ElemType date ;
struct LNode *next ;
} *Link, *Position ;

typedef struct { //链表类型
Link head,tail ; //分别指向线性链表中的头结点和最后一个结点
int len ; //指示线性链表中数据元素的个数
} LinkList ；

Status Excha-L ( LinkList &L, int i) {

for(int i = n; i>=1; i--)
{ s = L[i-1]*next;
InsFirst(head,s) ； } // 已知h指向线性链表的头结点，将s所指结点插入在第一个结点之前
L[0]*next = tail ;
return OK ;
} // Excha-L

3、由于线性表的长度可变，在C语言中可用动态分配的一维数组，一般情况下，
删除第i（(1≤i≤n)个元素）时需将从i+1 至第n（共n-i）个元素依次向前移动一个位置。如下描述：

#define LIST-SIZE maxlen // 线性表存储空间的初始分配量
typedef struct {
ElemType *elem ; // 存储空间基址
int length ; // 当前长度
int listsize ; // 当前分配的存储容量
} Stlist ;

Status Listdelete-St (Stlist &L, int i ，ElemType &e) {
// 在顺序线性表L中删除第i个元素，并用e返回其值
// i的合法值为1≤i≤ListLength-St
if ((i<1) || (i> L.length)) return ERROR ; // i值不合法
p = & (L.elem[i-1]) ; //p为被删除元素的位置
e = *p ; //被删除元素的值赋给e
q = L.elem + L.length -1 ; //表尾元素的位置
for (++p; p<=q ; ++p) * (p-1) = *p ; //被删除元素之后的元素左移
- -L.length ; //表长减1
return OK ;
} // ListDelete - St本回答被提问者采纳