西华大学数据结构参考答案A

助人教育QQ：数据结构试题一、单项选择题1．数据结构是（D）A．一种数据类型B．数据的存储结构C．一组性质相同的数据元素的集合D．相互之间存在一种或多种特定关系的数据元素的集合2．算法分析的目的是（B）A．辨别数据结构的合理性B．评价算法的效率C．研究算法中输入与输出的关系D．鉴别算法的可读性3．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（D）A．插入B．删除C．排序D．定位4．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（A）A．1207 B．1209C．1211 D．12135．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（A）A．不一定相同B．都相同C．都不相同D．互为逆序6．若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（C）A．层次遍历算法B．前序遍历算法C．中序遍历算法D．后序遍历算法7．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（A）A．图中每个顶点的入度B．图中每个顶点的出度C．图中弧的条数D．图中连通分量的数目8．图的邻接矩阵表示法适用于表示（C）A．无向图B．有向图C．稠密图D．稀疏图9．在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i 趟排序之前，无序区中关键字元素的个数为（D）A．i B．i+1C．n-i D．n-i+110．下列排序算法中，其时间复杂度和记录的初始排列无关的是（B）A．插入排序D．冒泡排序11．若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（A）A．f,c,b B．f,d,b C．g,c,b D．g,d,b12．若在文件中查询年龄在60岁以上的男性及年龄在55岁以上的女性的所有记录，则查询条件为（C）A．（性别=“男”）OR(年龄> 60)OR（性别=“女”）OR（年龄>55）B．（性别=“男”）OR(年龄> 60)AND（性别=“女”）OR（年龄>55）C．（性别=“男”）AND(年龄> 60)OR（性别=“女”）AND（年龄>55）D．（性别=“男”）AND(年龄> 60)AND（性别=“女”）AND（年龄>55）13．设单链表中结点的结构为typedef struct node { //链表结点定义ElemType data；//数据struct node * Link；//结点后继指针} ListNode；（1）已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？BA. 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；（2）非空的循环单链表first的尾结点（由p所指向）满足：CA. p->link == NULL；B. p == NULL；C. p->link == first；D. p == first；二、填空题14．称算法的时间复杂度为O(f(n))，其含义是指算法的执行时间和__ f(n)_____的数量级相同。

数据结构习题及解答第1章 概述【例1-1】分析以下程序段的时间复杂度。

for(i=0;i<n;i++)for(j=0;j<m;j++) A[i][j]=0;解：该程序段的时间复杂度为O (m*n )。

【例1-2】分析以下程序段的时间复杂度。

i=s=0; ①while(s<n){ i++; ②s+=i; ③}解：语句①为赋值语句，其执行次数为1次，所以其时间复杂度为O (1)。

语句②和语句③构成while 循环语句的循环体，它们的执行次数由循环控制条件中s 与n 的值确定。

假定循环重复执行x 次后结束， 则语句②和语句③各重复执行了x 次。

其时间复杂度按线性累加规则为O (x )。

此时s 与n 满足关系式：s ≥n ，而s=1+2+3+…+x 。

所以有：1+2+3+…+x ≥n ，可以推出：x=n n 241212811+±-=+±-x 与n 之间满足x=f(n ），所以循环体的时间复杂度为O (n )，语句①与循环体由线性累加规则得到该程序段的时间复杂度为O (n ）。

【例1-3】分析以下程序段的时间复杂度。

i=1; ①while(i<=n) i=2*i; ②解：其中语句①的执行次数是1，设语句②的执行次数为f (n )，则有：n n f ≤)(2。

得：T（n）=O(n2 log)【例1-4】有如下递归函数fact(n)，分析其时间复杂度。

fact(int n){ if(n<=1) return(1); ①elsereturn(n*fact(n-1)); ②}解：设fact（n）的运行时间函数是T(n)。

该函数中语句①的运行时间是O(1)，语句②的运行时间是T(n-1)+ O(1)，其中O(1)为常量运行时间。

由此可得fact（n）的时间复杂度为O(n)。

习题1一、单项选择题1.数据结构是指（1. A ）。

A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（2. C ）。

数据结构习题及参考答案一、概述在计算机科学领域，数据结构是指组织和存储数据的方式，以便于有效地访问和操作。

它是计算机算法和程序设计的基础。

下面将介绍一些常见的数据结构习题，并提供相应的参考答案，帮助读者更好地理解和掌握数据结构。

二、数组1. 习题：给定一个数组，编写一个函数来计算数组中元素的和。

【参考答案】```pythondef sum_array(arr):sum = 0for num in arr:sum += numreturn sum```三、链表1. 习题：给定一个链表，反转链表，并返回反转后的头节点。

【参考答案】```pythonclass ListNode:def __init__(self, val=0, next=None): self.val = valself.next = nextdef reverse_linked_list(head):prev = Nonecurr = headwhile curr:next_node = curr.nextcurr.next = prevprev = currcurr = next_nodereturn prev```四、栈和队列1. 习题：使用栈实现队列的功能。

【参考答案】```pythonclass MyQueue:def __init__(self):self.stack1 = []self.stack2 = []def push(self, x):self.stack1.append(x)def pop(self):if not self.stack2:while self.stack1:self.stack2.append(self.stack1.pop())return self.stack2.pop()def peek(self):if not self.stack2:while self.stack1:self.stack2.append(self.stack1.pop())return self.stack2[-1]def empty(self):return len(self.stack1) == 0 and len(self.stack2) == 0 ```五、树1. 习题：给定一个二叉树，判断它是否是高度平衡的。

数据结构试题参考答案第一章绪论一、选择题：二、填空题：1、（l）结点的集合（2）结点有序对的集合2、（l）开始结点（2）终端结点3、（l）线性结构（2）非线性结构4、前驱5、顺序方法或索引方法6、顺序7、（l）逻辑结构（2）存储8、时间复杂度9、问题规模10、数组11、（1）数据元素（2）数据元素间关系12、（1）集合（2）线性结构（3）树形结构（4）图状结构或网状结构。

13、（1）有穷性（2）确定性（3）可行性。

14、O(n)15、（1）一对一（2）一对多（3）多对多三、判断题（正确的在括号中记√，错误的记×）四、应用题1、评价好的算法有四个方面。

一是算法的正确性；二是算法的易读性；三是算法的健壮性；四是算法的时空效率（运行）。

2、将学号、姓名、平均成绩看成一个记录（元素，含三个数据项），将100个这样的记录存于数组中。

因一般无增删操作，故宜采用顺序存储。

typedef struct{int num;//学号char name[8];//姓名float score;/平均成绩}node；node student[100];3、应从两方面进行讨论：如通讯录较少变动（如城市私人电话号码），主要用于查询，以顺序存储较方便，既能顺序查找也可随机查找；若通讯录经常有增删操作，用链式存储结构较为合适，将每个人的情况作为一个元素（即一个结点存放一个人），设姓名作关键字，链表安排成有序表，这样可提高查询速度。

4、(1)O(1) (2)O(n2) (3)O(n3)五、综合题：1、struct node{int year,month,day; };typedef struct{int num;//帐号char name[8];//姓名struct node date;//开户年月日int tag;//储蓄类型，如：0- 零存，1- 一年定期……float put;//存入累加数；float interest;//利息float total;//帐面总数}count；2、第一层FOR循环判断n+1次，往下执行n次，第二层FOR执行次数为(n+(n-1)+(n-2)+…+1)，第三层循环体受第一层循环和第二层循环的控制，其执行次数如下表：i= 1 2 3 … nj=n n n n … nj=n-1 n-1 n-1 n-1 …… … … …j=3 3 3j=2 2 2j=1 1执行次数为(1+2+…+n)+(2+3+…+n)+…+n=n*n(n+1)/2-n(n2-1)/6。