当前位置：文档之家› 数据结构前两年的期中考试题型

数据结构前两年的期中考试题型

2010-2011第一学期数据结构期中考试题 [原

创 2010-10-29 12:36:57]

字号：大中小在以下题目中任意选择做

1．求下列程序段的时间复杂度（每小题5分,最多选做2题，多做不给分）

（1）i=1；

WHILE (i

（2）下面程序段的时间复杂度为( )

s=0；

for(i=1；i

for(j=1；j

s+=i*j；

（3）int x=n;

int y=0;

while(x>=(y+1)*(y+1))

y++;

2.按增长率从小到大顺序排列以下函数（5分）

1、按增长率由小至大的顺序排列下列各函数：

2100, (3/2)n, (2/3)n, n n , n(1/2), n! , 2n , lgn , n lgn , n(3/2)

3．问答题

(1)．若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？(5分)

(2)．双向链表中有两个指针域，prep和next，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，请写出其插入操作序列。（6分）(3)．设单链表的结点结构为（data,next），data为整数，next为指针域，已知指针px 指向单链表中data为x的结点，指针py指向data为y的新结点，请写出将py指向结点插入为px指向结点的直接后继所执行的语句。（6分）

(4). 若串S1=“I am a teacher”, S2=“teacher” ,S3=“student”执行

replace(S1,0，substr(S1,length(S2),length(S3)),S3)后，其结果是什么？（5分）（5）．假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为118，请求出Loc[5，15]的值。（5分）

（6）. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是多少？（5分）

（7）下列二分搜索算法BinarySearch是否正确，请说明原因。(6分)

int BinarySearch(Datatype a[],Datatype x,int n)

{

int left=0;int right=n-1;

int middle；

while(left<=right)

{

middle =(left+right)/2

if(x==a[middle])return middle;

if(x>a[middle])left=middle;

else right=middle;

}

return -1

}

（8)阅读下面的算法（15分）

LinkList mynote(LinkList L)

{//L是不带头结点的单链表的头指针

if(L&&L->next){

q=L；L=L－>next；p=L；

S1： while(p->next) p=p－>next；

S2： p－>next=q；q－>next=NULL；

}

return L；

}

请回答下列问题：

（1）说明语句S1的功能；

（2）说明语句组S2的功能；

（3）设链表表示的线性表为（a1,a2, …,an）,写出算法执行后的返回值所表示的线性表。

4．填空与选择

(1)．以下程序采用链表合并的方法，将两个已排序的单链表合并成一个链表而不改变其排序性（升序），这里两链表的头指针分别为p和q.(每空3分)

void mergelink(SLNode *p, SLNode *q)

{

SLNode *h,*r;

//建立头结点（1）______

h->next= NULL;

r=h;

while((p!=NULL)&& (q!=NULL)){

if (p->data<=q->data){

//（2）___；

r=p; p=p->next；

}

else{

//（3）____；

r=q; q:=q->next;

}

};

if(p==NULL) r->next=q;

//（4）____;

}

（以下选择题每题4分）

（1）下面程序段的时间复杂度为（）

int f(int n)

{if(n==0 || n==1) return 1;

else return n*f(n-1); }

A. O(1)

B. O(n)

C. O(n2)

D. O(n!)

（2）设栈的输入序列为（1，2，3，4），则（）不可能是输出序列。

A.1423

B.2134

C.1432

D.3214

（3）假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为( )

A.(rear-length+m+1)％m

B.(rear-length+m)％m

C.(rear-length+m-1)％m

D.(rear-length)％m

（4）判定一个顺序循环队列q（数据元素最多为Max）为队满的条件是（）。

A. q.real-q.front=Max

B.q.front=q.rear

C.q.rear-q.front-1=Max

D.q.front=(q.rear+1)%Max

5.程序设计题

1).已知两个单链表A和B,其头指针分别为heada和headb，编写一个函数从单链表A中删除自第i个元素起的共len个元素，然后将单链表A插入到单链表B的第j个元素之前。（15分）

2).设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，请编写一个函数判断t是否为s的子串。如果是，输出子串所在位置（第一个字符），否则输出0。(15分)

6．设有下列递归算法:

int vol(int n)

{

if(n==0) return 0;

else

return vol(n-1)+2;

}

如该函数被调用时，参数n值为3,函数调用结束时返回值为多少?用图示描述函数的递归调用执行过程。(15分)

2009－2010第一学期数据结构期中考试

[原创 2009-11-3 8:30:41]

字号：大中小在以下题目中任意选择做

1．求下列程序段的时间复杂度（每小题5分,最多选做2题，多做不给分）

（1）for(i=0;i

for(j=0; j

for(k=0; k

ｘ＝ｘ＋delta；

（2）i=1；

WHILE (i

（3） i=n*n

WHILE (i!=1) i=i/2;

2.按增长率从小到大顺序排列以下函数（5分）

n, n-n3+7n5, nlogn, 2n/2, n3, logn, n1/2+logn, (3/2)n, n!, n2+logn

3．问答题（最多选做7题，多做不给分）

(1)．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度分别为多少？(3分)

(2)．若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？(5分)

(3)．双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，请写出其插入操作序列。（6分）

(4)．在单链表和双向链表中，能否从当前结点出发访问到任何一个结点? (3分)

(5)．给出循环队列中元素个数的计算式(设队最大长度为N,队首指针FRONT，队尾指针REAR)。（5分）

(6). 若串S1=”ABCDEFGHIJK”, S2=”9898” ,S3=”###”执行

replace(S1,0，substr(S1,length(S2),length(S3)),S3)后，其结果是什么？（5分）（7）．假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，请求出Loc[5，5]的值。（5分）

（8）. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是多少？（5分）

4．填空与选择

(1)．以下程序采用链表合并的方法，将两个已排序的单链表合并成一个链表而不改变其排序性（升序），这里两链表的头指针分别为p和q.(每空3分)

void mergelink(SLNode *p, SLNode *q)

{

SLNode *h,*r;

//建立头结点（1）______

h->next= NULL;

r=h;

while((p!=NULL)&& (q!=NULL)){

if (p->data<=q->data){

//（2）___；

r=p; p=p->next；

}

else{

//（3）____；

r=q; q:=q->next;

}

};

if(p==NULL) r->next=q;

//（4）____;

}

（以下选择题每题4分）

(2)．一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。

A. 2 3 4 1 5

B. 5 4 1 3 2

C. 2 3 1 4 5

D. 1 5 4 3 2

(3) 输入序列为ABC，可以变为CBA时，经过的栈操作为（）

A. push,pop,push,pop,push,pop

B. push,push,push,pop,pop,pop

C. push,push,pop,pop,push,pop

D. push,pop,push,push,pop,pop

(4) 栈和队列的共同点是（）。

A. 都是先进先出

B. 都是先进后出

C. 只允许在端点处插入和删除元素

D. 没有共同点

（5）对稀疏矩阵进行压缩存储目的是（）

A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度5.程序设计题

（1）已知两个单链表A和B,其头指针分别为heada和headb，编写一个函数从单链表A中删除自第i个元素起的共len个元素，然后将单链表A插入到单链表B的第j个元素之前。（15分）

(2) 利用两个栈sl,s2模拟一个队列时，编程实现用栈的运算实现队列的插入，删除以及判队空运算。（15分）

（3）设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，请编写一个函数判断t是否为s的子串。如果是，输出子串所在位置（第一个字符），否则输出0。(10分)

6．设有下列递归算法:

int vol(int n)

{

if(n==0) return 0;

else

return vol(n-1)+2;

}

如该函数被调用时，参数n值为3,函数调用结束时返回值为多少?用图示描述函数的递归调用执行过程。(12分)

数据结构期中考试模试卷2014

数据结构模拟试卷一. 单选题（每题1分，共14分） 1．数据结构所讨论的基本数据单位是（B）。 A、数据对象 B、数据元素 C、数据项 D、数据类 2. 在数据结构的讨论中把数据结构从逻辑上分为（C）两大类。 A.内部结构与外部结构 B.静态结构与动态结构 C.线性结构与非线性结构 D.紧凑结构与非紧凑结构。 3．若一个算法的时间复杂度用T(n)表示，其中n的含义是（ A ）A．问题规模B．指令条数 C．循环层数D．函数数量 4. 算法分析的目的是（C）。 A. 研究算法的输入与输出之间的关系 B. 找出数据结构的合理性 C. 分析算法的效率以求改进算法 D. 分析算法的可读性与可移植性 5、采用线性链表表示一个向量时，要求占用的存储空间地址（D） A.必须是连续的 B.部分地址必须是连续 C. 一定是不连续的 D. 可连续可不连续 6. 在一个当前长度为n的顺序表中向第j个元素（1next＝＝NULL C、head一>next= = head D、head!＝NULL 8、设单链表中指针P指向结点A，若要删除A之后的结点（若存在），则需要修改指针的操作为（A） A、p→next=p→next→next B、p=p→next C、p=p→next→next D、p→next=p 9、若有一个最大长度为size，且设有队首指针front和队尾指针rear的顺序循环队列，试问判断队列满的条件应是下列哪一个语句（D） A、front==rear B、front- rear==size C、front+rear==size; D、front==(rear+1)%size

数据分析期末试题及答案

数据分析期末试题及答案一、人口现状.sav数据中是1992年亚洲各国家和地区平均寿命(y)、按购买力计算的人均GDP(x1)、成人识字率(x2)，一岁儿童疫苗接种率(x3)的数据，试用多元回归分析的方法分析各国家和地区平均寿命与人均GDP、成人识字率、一岁儿童疫苗接种率的关系。(25分) 解： 1.通过分别绘制地区平均寿命(y)、按购买力计算的人均GDP(x1)、成人识字率(x2)，一岁儿童疫苗接种率(x3)之间散点图初步分析他们之间的关系上图是以人均GDP(x1)为横轴，地区平均寿命(y)为纵轴的散点图，由图可知，他们之间没有呈线性关系。尝试多种模型后采用曲线估计，得出表示地区平均寿命(y)与人均GDP(x1)的对数有线性关系

上图是以成人识字率(x2)为横轴，地区平均寿命(y)为纵轴的散点图，由图可知，他们之间基本呈正线性关系。上图是以疫苗接种率(x3)为横轴，地区平均寿命(y)为纵轴的散点图，由图可知，他们之间没有呈线性关系。 x）为横轴，地区平均寿命(y)为纵轴的散点图，上图是以疫苗接种率(x3)的三次方（3 3 由图可知，他们之间呈正线性关系所以可以采用如下的线性回归方法分析。

2.线性回归先用强行进入的方式建立如下线性方程设Y=β0+β1*（Xi1）+β2*Xi2+β3* X+εi i=1.2 (24) 3i 其中εi（i=1.2……22）相互独立，都服从正态分布N（0，σ^2）且假设其等于方差 R值为0.952，大于0.8，表示两变量间有较强的线性关系。且表示平均寿命(y)的95.2%的信息能由人均GDP(x1)、成人识字率(x2)，一岁儿童疫苗接种率(x3)一起表示出来。建立总体性的假设检验提出假设检验H0：β1=β2=β3=0，H1,：其中至少有一个非零得如下方差分析表上表是方差分析SAS输出结果。由表知，采用的是F分布，F=58.190，对应的检验概率P值是0.000.，小于显著性水平0.05，拒绝原假设，表示总体性假设检验通过了，平均寿命(y)与人均GDP(x1)、成人识字率(x2)，一岁儿童疫苗接种率(x3)之间有高度显著的的线性回归关系。

2017年数据结构期末考试题及答案A

2017年数据结构期末考试题及答案一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出

8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点

2010年数据结构期中考试试卷及答案

《数据结构》期中试卷（2009级） 2010-2011学年第一学期姓名：学号：成绩：一、选择题：（每小题2分，共20分） 1.有六个元素6，5，4，3，2，1 的顺序进栈，下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 2.在一个有125个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。 A．8 B. 62.5 C. 62 D. 7 3. 已知广义表A＝((a,b,c),(d,e,f),(h,(i,j)),g)，从A表中取出原子项e的运算是：( ) A.head(tail(A)) B.head(tail(tail(A))) C.head(head(tail(tail(A)))) D.head(tail(head(tail(A)))) 4.循环队列存储在数组A[0..m]中，设front和rear分别为队列的头指针和尾指针，则入队时的操作为（）。 A. front=( front +1) mod (m+1) B. rear=(rear+1) mod (m+1) C. front=( front +1) mod m D. rear=(rear+1) mod m 5. 在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是( ) (假设双向循环链表的结点结构为(llink,data,rlink)。A．p->llink=q； q->rlink=p；p->llink->rlink=q；q->llink=q； B．p->llink=q；p->llink->rlink=q ；q->rlink= p；q->llink=p->llink； C．q->rlink=p；q->llink=p->llink；p->llink->rlink=q; p->llink=q; D．q->llink=p->llink；q->rlink=p；p->llink=q；p->llink=q； 6. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。 A．250 B．500 C．254 D．以上答案都不对 7. 已知一棵二叉树的前序遍历结果为ABCDEF, 中序遍历结果为CBAEDF, 则后序遍历的结果为（）。 A．CBEFDA B．FEDCBA C．CBEDFA D．不定 8. 利用二叉链表存储树时，则根结点的右指针是（）。 A．指向最左孩子B．指向最右孩子C．空D．非空 9.设有二维数组A[0..9, 0..19], 其中每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6,6]存储地址为( )。 A. 252 B. 132 C. 352 D.232 10. 引入二叉线索树的目的是（） A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一

如何对学生考试成绩进行数据分析

一、原始分和标准分的定义原始分是考试后直接从卷面上得到的分数。标准分是指通过原始分转化而得到的一种地位量数，它反映考生成绩在全体考生成绩中的位置。因此，无论试题难或易，无论整体原始分偏高或偏低，整体标准分都没有什么变化。二、标准分的计算根据教育统计学的原理，标准分Z是原始分与平均分的离差以标准差为单位的分数，用公式表示为：Z=(X-A)/S 其中：X为该次考试中考生个人所得的原始分；A为该次考试中全体考生的平均分；S为该次考试分数的标准差。通过转换后得到的标准分Z在一般情况下都带小数，而且会出现负值，实际使用时不太方便，所以还要对Z分数进行线性变换（T变换）：T=500+100Z 这就是我们通常所说的标准分。这种标准分的平均值为500，也就是说，如果某考生的标准分为500，则该生的成绩处于此次考试的中间位置。标准分有如下性质： ⑴平均值为0，标准差为1； ⑵分数之间等距，可以作加减运算； ⑶原始分转换为标准分是线性转换，不会改变原始分的分布形状，也不改变原来分数的位置次序。三、使用标准分比使用原始分有什么好处？根据教育统计学的原理，原始分转换成标准分的意义可以从下面的比较中反映出来： ⑴单个标准分能够反映考生成绩在全体考生成绩中的位置，而单个原始分则不能。例如，某考生某科的原始成绩为85分，无法说明其这科成绩究竟如何，因为这与试题的难度有关，与总体考生的分数有关。如果某考生某科的标准分为650，即Z分数为1.5，则通过查正态分布表，查得对应的百分比为0.9332，于是我们知道，该考生的成绩超过了93.32%的考生的成绩，这就是分数解释的标准化。 ⑵不同学科的原始分不可比，而不同学科的标准分是可比的。不同的学科，由于试题的难易程度不同，各学科的分数价值也就不同。例如某考生的语文原始成绩为80分，数学原始成绩为70分，从原始分看，其语文成绩优于数学成绩。但如果这次考试全体考生的语文原始分平均为86分，而数学原始分平均为60分，则该考生的语文成绩处于全体考生的平均水平之下，而数学成绩处于全体考生的平均水平之上，即该生的数学成绩实质上优于语文成绩。从标准分的角度来衡量，其语文标准分小于500分，而数学标准分大于500分。由于标准分代表了原始分在整体原始分中的位置，因此是可比的。 ⑶不同学科的原始分不可加，而不同学科的标准分之间具有可加性。既然不同学科的原始分不可比，那么也就不可加。多学科成绩，只有在各科成绩的平均值相同、标准差也相同的条件下，才能相加，否则是不科学的。各学科原始分的平均值以及标准差一般都不相同，而各学科的标准分的平均值以及标准差都基本相同，因此，各科的标准分是可加的。四、什么是增值? 教学增值就是评价时将学生原有基础一并考虑，用以比较原有基础与接受教师教育后成绩增进的幅度。增值评价分为两步：首先根据原有基础得到一个

数据结构期中试题及参考答案

淮海工学院 2009 - 2010 学年第 1 学期数据结构期中试卷 ( 闭卷)题号一二三四五六七八九总分得分一、单项选择题（本大题共12小题，每小题2分，共24分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。选错、多选或未选均无分。 1.按值可分解，数据类型通常可分为两类，他们是【 C 】A．静态类型和动态类型 B. 原子类型和表类型C．原子类型和结构类型 D. 数据类型和指针类型 2.对于三个函数f(n)=2008+8+96000，g(n)=8+8n+2008和 h(n)=8888n+3n2，下列陈述中不成立的是【C 】A. f(n)是O(g(n)) B. g(n)是O(f(n)) C. h(n)是O(n) D. h(n)是O() 3.指针p、q和r依次指向某循环链表中三个相邻的节点，交换节点*q和节点*r在表中的次序的程序段是【 A 】 A. p->next=r; q->next=r->next; r->next=q; B. p->next=r; r->next=q; q->next=r->next; C. r->next=q; q->next=r->next; p->next=r; D. r->next=q; p->next=r; q->next=r->next; 4.若进栈次序为a ,b ,c,且进栈和出站可以穿插进行，则可能出现的含个元素的出站序列个数是【 B 】A．3 B．5 C．6 D．7 5.假设以数组A[n]存放循环队列的元素，其头指针front指向队头元素的前一个位置、为指针rear指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为【 D 】A．rear==front B. (front+1)%n==rear C. rear+1==front D.(rear+1)%n==front 6.串的操作函数str定义为： int str (char *s) { char *p=s; while (*p!=’\0’) p++; return p-s; } 则str(“abcde”)的返回值是【 C 】A．3 B．4 C．5 D．6 7.二维数组A[10][6]采用行优先的存储方法，若每个元素占4个存储单元，已知元素A[3][4]的存储地址为1000，则元素A[4][3]的存储地址为【 A 】A．1020 B．1024 C．1036 D．1240 8.对广义表L=(a,())执行操作tail(L)的结果是【 B 】A．() B．(()) C．a D．(a) 9.已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为【A】 A. FEDCBA B. ABCDEF C. FDECBA D. FBDCEA 10.已知森林F={,,,,},各棵树(i=1，2，3，4，5)中所含节点的个数分别为7，3，5，1，2，则与F对应的二叉树的右子树种的节点个数为【 D 】A．2 B．3 C．8 D．11 11.若非连通无向图G含有21条边，则G的顶点个数至少为【 B 】 A．7 B．8 C．21 D．22 12.如图所示的有向图的拓扑序列是【B 】 A. c , d , b , a , e B. c , a , d , b , e C. c , d , e , a , b D. c , a , b , d , e a b e d 题12图 c １

苏州大学数据结构课程期中考试答案

苏州大学数据结构课程期中考试（共6页）学院计算机专业计算机科学与技术成绩____________________ 班级11计科学号_____________姓名_____________日期2012.11_ 一、填空（14*2 分） 1 x=n; y=0; while (x>=y*y) y=y+1; 2、对于顺序存储的栈，因为栈的空间是有限的，在进行入栈运算时，可能发生栈的上溢（overflow），在进行出栈 _运算时，可能发生栈的下溢(underflow)。 3、以顺序结构实现的双栈类中，其私有数据成员数组S[0..n-1]存放两个栈中的所有元素，top1和top2分别指向两个栈的栈顶位置，入栈1时top1由小到大，入栈2时top2由大到小，则判断双栈栈满的条件是top1+1>=top2 ，双栈栈空的条件是top1==-1 && top2==n。 4、完成链式存储结构下Queue类的append方法，其中front和rear指针分别指示队首和队尾结点： Error_code Queue :: append(const Queue_entry &item) { Node *new_rear = new Node(item); if (new_rear == NULL) return overflow; if (rear == NULL) front=rear=new_rear; ; else { rear->next=new_rear; ； rear = new_rear; } return success; } 5、如果一个函数直接或间接地调用自己，则称这个函数是一个递归函数。

数据结构期末考试题及标准答案

————————————————————————————————作者：————————————————————————————————日期：

2012年数据结构期末考试题及答案一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。

s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。

数据结构期中考试试题答案c语言版本

数据结构期中考试试题答案一、单选题（每小题2分，共8分） 1.在一个长度为n的线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为 C 。 A.n B.n/2 C.(n+1)/2 D.(n-1)/2 2.在一个带附加表头的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行 D 。 A.HL=p;p->next=HL; B.p->next=HL;HL=p; C.p->next=HL;p=HL; D.p->next=HL->next;HL ->next=p; 3．若让元素A，B，C，D依次入栈，则出栈次序不可能出现 D 种情况。 A.D,C,B,A B.A,D,C,B C.B,A,D,C D.D,A,B,C 4．从一个顺序队列删除元素时，首先需要 B 。 A.前移一位队首指针 B.后移一位队首指针 C.取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素二、填空题（每空1分，共32分） 1．数据的逻辑结构分为集合、线性、树型、图形四种。 2.函数重载要求参数个数、参数类型或参数次序有所不同。 3．在带附加表头的循环双向链表中，表头附加结点的左指针域指向最后一个结点，最后一个结点的右指针域指向表头附加结点。

4．在以HL为表头指针的带附加结点的单链表和循环单链表中，链表为空的条件分别为 HL->next==NULL 和 HL==HL->next 。 5．在由数组a中元素结点构成的单链表中，删除下标为i的结点后，需要把该结点插入到空闲表的表头，具体操作为 a[i].next=a[1].next 、a[1].next=i 。 6．在由数组a中元素结点构成的单链表中，删除下标为i的结点的后继结点并将被删除结点的下标赋给i时，所进行的操作（需要用一个临时变量p）描述为 p=a[i].next 和 a[i].next=a[p].next;i=p 。 7．在稀疏矩阵的十字链接存储中，每个结点的down指针域指向列号相同的下一个结点，right指针域指向行号相同的下一个结点。 8．一个广义表中的元素分为单元素和表元素两类。 9．广义表A=((a,(b,(),c),((d),e)))的长度为 1 ，深度为 4 。 10．向一个顺序栈插入一个元素时，首先应 top++ ，然后再将待插入元素放入栈顶位置。 11．对于队列，应在队尾进行插入，在队首进行删除。 12．中缀表达式2+7/(4-1)所对应的后缀表达式为 2 7 4 1 - / + @ 。 13．后缀表达式“10 3 5 4 - * - 1 + 3 2 + -”的值为 3 。 14.一棵二叉树的广义表表示为a(b(c,d),e(f(,g))),则e结点的双亲结点为 a ，孩子结点为 f ，树的深度为 4 。三、运算题（每小题8分，共24分） 1．假定线性表L=（33,69,78,22,44,88）,i=3,x=34,y=22,则对L进行下列一组操作` ListEmpty(L); false GetElem(L,i); 78

数据结构期中试卷信息11)2015-1-21 16.12.11

嘉兴学院试卷 2012—2013 学年第1 学期期中考试试卷课程名称：数据结构使用班级：信息11级考试形式：开卷试卷代码：班级：姓名：学号：一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。每小题1分，共10分) 1．数据的逻辑结构从形式上可用二元组（D，R）表示，其中R是（ D ）的有限集。 A．算法B．数据元素C．数据操作D．数据关系 2．数据结构课程研究的内容涉及到三个方面的内容，它们分别是数据的逻辑结构、数据的（C）和数据的操作。 A．数据元素B．逻辑结构C．存储结构D．计算方法 3．线性结构的顺序存储结构是一种随机存取的存储结构，而链式存储结构是一种（ A ）的存储结构。 A．顺序存取 B．随机存取 C．索引存取 D．散列存取 4．线性表L在（ B ）情况下，最适合采用链式存储结构来实现算法。 A．不需经常对L进行修改 B．需经常对L进行删除和插入操作 C．需经常修改L中结点值 D．L中结点结构复杂 5．在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（ C ）。 A.O(1) B. O(log2n) C. O(n) D. O(n2) 6．在循环顺序队列中，假设以设置一个计数变量num的方法来区分队列判满和判空的条件，front和rear 分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则下面不是队列判满或判空条件是（ A ）。 A．front==rear B. front= =rear && num==0 C. front= =rear && num>0 D. num= =maxSize 7．一个栈的入栈序列是a, b, c, d, e, 则栈的不可能的出栈序列是（ D ）。 A．abcde B．decba C．edcba D．dceab 8．在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是（ C ）。 A．top = =0 B.top= =-1 C. top = =maxSize D.top = = maxSize-1 9．设线性表有n个元素，严格说来，以下操作中，（ B ）在顺序表上实现比链表上实现比链表上实现效率更高。 Ⅰ输出第i个（0≤i≤n-1）数据元素的值 Ⅱ交换第3个数据元素与第4个数据元素的值 Ⅲ顺序输出这n个数据元素的值 A．Ⅰ B．Ⅰ、Ⅱ C．Ⅰ、Ⅲ D．Ⅱ、Ⅲ 10. 在一个单链表中的p和q两个结点之间插入一个新结点，假设新结点为s,则修改链的Java语句序列是（ D ）。 A．s.setNext(p); q.setNext(s); B. p.setNext(s.getNext()); s.setNext(p); C. q.setNext(s.getNext()); s.setNext(p); D. p.setNext(s); s.setNext(q); 二、填空题（20分，每空1分） 1．算法的复杂度通常体现为时间复杂度和空间复杂度两个指标。 2．设有函数T (n)=3n2-n+4，T (n)=O ( n2)。 3．要将一个顺序表{a0,a1,……,a n-1}中第i个数据元素a i(0≤i≤n-1)删除，会引起n-1-i个数据元素的移动。 4．队列也是一种操作受限的线性表，它与栈不同的是，队列中所有的插入操作均限制在表的一端进行，而所有的删除操作都限制在表的另一端进行，允许插入的一端称为队尾，允许删除的一端称为队首。队列具有先进先出的特点。 5．在一个单链表中删除p所指结点时，可执行如下操作： q=p.getNext(); p.setData(q.getData());p.setNext( q.getNext() ); 6．设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出栈的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是3。 7．若双向链表的结点类描述为：public class DuLNode { pvivate Object data; private DuLNode piror; private DuLNode next; …… } 则在带头结点的双向链表中的p结点之前插入一个新结点s，其修改指针的java语句序列是： 1）p.getPiror().setNext(s); 2）s.setPiror(p.gettPiror()); 3）s.setNext(p); 4）p.setPiror(s); 8．在不带表头结点的链栈中，栈顶指针top直接指向栈顶元素，如果链栈中结点的类描述为： class Node { 命题人或命题小组负责人签名：所（室、教研部）负责人签名：分院（部）领导签名：

数据结构与算法期中考试题

一、单选题, 从可供选择的4个答案中, 选择一个正确的答案, 将其前面的字母填写在( )中,共40分,每小题4分。 1.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p 之间插入s结点，则执行( )。 A.s->next=p->next; p->next=s; B.q->next=s; s->next=p; C.p->next=s->next; s->next=p; D.p->next=s; s->next=q; 2.带头结点的单链表为空的判定条件是( )。 A.head= =NULL B.head->next= =NULL C.head->next= =head D.head!=NULL 3. 若一棵完全二叉树中某结点无左孩子，则该结点一定是（）。 A．度为１的结点B．度为２的结点C．叶子结点 D．分支结点 4.设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是( )。 A．a在b的右方B．a在b的左方C．a是b的祖先D．a是b的子孙5．在长度为n的线性表中查找值为x的数据元素的时间复杂度为：（）。 A. O(0) B. O(1) C. O(n) D. O(n2) 6．一个栈的入栈序列是a, b, c, d, e，则栈的不可能的出栈序列是（）。 A. edcba B. cdeba C.debca D.abcde 7．前序遍历和中序遍历结果相同的二叉树是（）。 A. 根结点无左孩子的二叉树 B. 根结点无右孩子的二叉树 C. 所有结点只有左子树的二叉树 D. 所有结点只有右子树的二叉树 8.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1] ~ A[n] 中，结点A[i]若有左子树，则左子树的根结点是（）。 A. A[2i-1] B.A[2i+1] C.A[i/2] D.A[2i] 9.对任何一棵四叉树T，如果其终端结点的个数为n0，度为2的结点个数为 n2，度为3的结点个数为n3,度为4的结点个数为n4,则（）。 A.n0=n2+n3+n4+1 B.n0=n2+2n3+3n4+1 C.n0=n1+n2+2n3+3n4+1 D.没有规律 10.算法指的是（）。 A. 对特定问题求解步骤的一种描述 B. 计算机程序 C. 解决问题的计算方法 D. 数据处理二、填空题, 请将答案填写在题目的( )内。（共24分，每小题6分） 1．在一个长度为n的顺序表的第i（1≤i≤n+1）个元素之前插入一个元素，需向后移动（）个元素，删除第i（1≤i≤n）个元素时，需向前移动（）个元素。 2. 权值为{2, 4, 1,7, 3，5}的叶子结点生成一棵哈夫曼树，其带权路径长度为（）。 3. 已知一棵二叉树的前序遍历序列为ABCDEFGH，中序遍历序列为CDBAFEHG，该二叉树的后序遍历序列是（）

《数据分析》课程期末考试试题A卷

命题方式：单独命题佛山科学技术学院2008—2009学年第一学期《数据分析》课程期末考试试题A卷专业、班级：姓名：学号：

共 3 页第 2 页

共 3 页第3 页

一（1）SAS界面包括输出框，日志框，编辑器（2）在非数值变量后面家上”$”符号. (3) 自由格式输入数据应加上”@@”标记. (4) 三均值的计算公式 ^ M=1/4Q1+1/2M+1/4Q3 二程序： data t1; input x@@; cards; 100.00 107.57 112.42 96.21 121.58 107.21 117.16 116.19 101.37 109.78 112.83 104.37 105.40 109.50 111.60 112.10 113.50 112.40 proc univariate plot normal; run; proc capability graphics normal; histogram x/normal; qqplot x/normal(….); run; （1）由上图可知道均值：109.510556 方差：40.5703938 变异系数：5.81632451 峰度：0.05978054 偏度：-0.3324812 （2）中位数：上四分位数：下四分位数：四分位极差：（3）做出直方图、QQ图、茎叶图、箱线图直方图：

QQ图茎叶图：

箱线图： (4)进行正态性W 检验（取05.0=α）．由上图可以知道Wo=0.978265,P=0.9304>05.0=α; 故不能拒绝原假设Ho,所以是高度显著的。三 data t2; input x1-x4; cards ; 16.7 26.7 6.4 35.0 18.2 28.0 3.2 29.7 16.7 26.7 2.1 34.9 18.1 26.7 4.3 31.5 16.7 26.0 3.0 32.7 18.1 30.2 7.0 34.9 20.2 30.5 4.8 34.4 20.2 29.5 5.5 36.2 21.5 31.5 5.8 36.5 18.8 30.6 5.4 35.4 21.6 27.8 5.4 34.1 21.3 29.5 5.8 35.8 proc corr cov pearson ; run ; (1)计算协方差矩阵，Pearson 相关矩阵；协方差矩阵：

清华大学数据结构试题及答案

一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是 ___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。 5. 5.设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j从0到3 ，则二维数组W的数据元素共占用＿_____＿个字节。W中第6 行的元素和第4 列的元素共占用＿_______＿个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿________＿。 6. 6.广义表A= (a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。 7.7.二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其所有结点的度的总和是_____________。 8.8.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。

数据结构期中作业

数据结构期中作业文档编制序号：[KKIDT-LLE0828-LLETD298-POI08]

北京邮电大学远程教育计算机科学与技术专业《数据结构》实验指导书实验一线性表的插入和删除一、实验目的 1、掌握用Turbo C上机调试线性表的基本方法； 2、掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。二、实验内容线性表基本操作的实现当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表的第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若要删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。程序实现： typedef Null 0; typedef int datatype; #define maxsize 1024; typedef struct { datatype data[maxsize]; int last; }sequenlist; int insert(L, x, i) sequenlist *L; int i; { int j; if ((*L).last= =maxsize-1) { printf(“overflow”); return Null; }

else if ((i<1)‖(i>(*L).last+1) { printf(“error”); return Null; } else { for(j=(*L).last; j>=i-1; j--) (*L).data[j+1]=(*L).data[j]; (*L).data[i-1]=x; (*L).last=(*L).last+1; } return(1); } int delete(L,i) sequenlist *L; int i; { int j; if ((i<1)‖(i>(*L).last+1)) {printf (“error”); return Null; } else { for(j=i, j<=(*L).last; j++) (*L).data[j-1]=(*L).data[j]; (*L).data - -; } return(1); } void creatlist( ) { sequenlist *L;

文档之家