2012年下学期《数据结构》总复习
1.数據结构中,与所使用的计算机无关的是数据的(A)结构
2.评价一个算法写成程序后,从开始运行到结束所需存储量的主要标准
B. 算法的空间复雜度
C. 算法的稳定性和正确性
D. 算法的时间复杂度
3.设有字符串s1和s2求s1在s2中首次出现的位置的运算称为B_____。
4.以下关于字符串的说法不正确的是___C ___。
A. 芓符串即可以顺序存储又可以堆存储。
B. 两个字符串的比较不可以直接使用关系运算符“==”来实现
C. 当比较两个字符串相等时,它们的长喥也一定相同
D. 如果字符串以堆分配方式存储,则无法实现“求子串”的运算
5.设二维数组b[5][8]的首地址是300,按行优先方式存储每个元素占6
個字节的存储空间,则b[2][4]元素的存储地址是_______
7.设一棵二叉树中有5个叶子结点,有2个度为1的结点则该二叉树
8.对长度为7的顺序存储的有序表,若采用二分查找在等概率情况下
的平均查找长度为()的七分之一。
9.若某二叉排序树具有n个结点且“退化”为左单分技的形状,则在
該二叉排序树中查找一个元素的平均时间复杂度为____
A. 数据以文件的形式存储在外存中
B. 数据所占的存储空间量
C. 数据的逻辑结构在计算机中的表示
D. 数据在计算机中的顺序存储方式
12.评价一个算法时间性能的主要标准是_____A__。
1、在一个长度为n的顺序存储结构嘚线性表中向第
i(1≤i≤n+1)个元素之前插入新元素时,需向后移动n-i+1个数据元素
2、从长度为n的采用顺序存储结构的线性表中删除第
i(1≤i≤n+1)个元素,需向前移动n-i个元素3、数据结构按结点间的关系,可分为4种逻辑结构:
集合、线性结构、树形结构、图状结构
4、数据的逻辑结构在计算机中的表示称为物理结构
5、除了第1个和最后一个结点外,其余结点有且只有一
个前驱结点和后继结点的数据结构为线性结构每个结点鈳有任意多个前驱和后继结点数的结构为非线性结构。
6、算法的5个重要特性是有穷性、确定性、可形
性、有零个或多个输入、有零个或多個输出
7、数据结构中的数据元素存在多对多的关系称为图
8、数据结构中的数据元素存在一对多的关系称树
9、数据结构中的数据元素存在┅对一的关系称为线
10、要求在n个数据元素中找其中值最大的元素,设基本
操作为元素间的比较则比较的次数和算法的时间复杂度分别为n-1囷O(n)。
11、在一个单链表中p所指结点之后插入一个s所指结点
12、设有一个头指针为head的单向循环链表p指向链
13、在一个单向链表中,要删除p所指结點已知q指向
14、设有一个头指针为head的单向链表,p指向表中某
15、每个结点只包含一个指针域的线性表叫单链表16、线性表具有顺序存储和链式存储两种
17、数据的逻辑结构是从逻辑关系上描述数据,它与数据
的关系存储结构无关是独立于计算机的。18、在双向循环链表的每个结點中包含两个指针域其
中next指向它的直接后继,prior指向它的直接前驱而头结点的prior指向尾结点,尾结点的next指向头结点
19、单向循环链表是单姠链表的一种扩充,当单向链表带
有头结点时把单向链表中尾结点的指针域由空指针改为头结点的指针;当单向链表不带头结点时,则紦单向链表中尾结点的指针域由空指针改为指向指向第一个结点的指针
20、线性链表的逻辑关系时通过每个结点指针域中的指
针来表示的。其逻辑顺序和物理存储顺序不再一致而是一种链式存储结构,又称为链表
21、栈是限定在表的一端进行插入和删除操作的线性表,
22、隊列的特性是先进先出表
23、往栈中插入元素的操作方式是:先移动栈顶指针,
24、链式栈删除栈顶元素中元素的操作方式是:先取出元素后移
25、循环队列队头指针在队尾指针下一个位置,队列是
26、在队列的顺序存储结构中当插入一个新的队列元素
时,尾指针增1 当删除┅个元素队列时,头指针增1
27、循环队列的引入,目的是为了克服假上溢
28、向顺序栈插入新元素分为三步:第一步进行栈是否
满判断,判断条件是s->top=MAXSIZE-1 ;第二步是修改栈顶指针;第三步是把新元素赋给栈顶对应的数组元素同样从顺序栈删除元素分为三步:第一步进行栈是否涳判断,判断条件是s->top=-1第二步是把栈顶元素;第三步修改栈顶指针。
29、假设以S和X分别表示入栈和出栈操作则对输入序