Paxon Qiao's Tech Blog

《数据结构》

· 17min · Paxon Qiao
Table of Contents

《数据结构》学习笔记

  1. 在循环双向链表的p所指结点之后插入s所指结点的操作是 s->left=p;s->right=p->right;p->right->left=s;p->right=s;
  2. 从一个具有n个结点的单链表中查找其值等于x结点是，在查找成功的情况下，需要比较 ( )个结点 (n+1)/2
  3. 在一个链对中，假设f和r分别为队首和队尾指针，则删除一个结点的运算是 f=f->next;
  4. 设串s1=‘ABCDEFG’，s2=‘PQRST’，函数con（x，y）返回x和y串的连接串，subs（s，i，j）返回串s的从序号id字符开始的j个字符组成的子串，len(s)返回串s的长度。则con(subs(s1，2，len(s2))，subs(s1，len(s2)，2))的结果是 BCDEFEF
  5. 数组的两种基本操作是 查找和修改
  6. 二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围是0到4,列下标j的范围是0到5,M按行存储时元素M[3][5]的起始地址与M按列存储时的元素( )的起始地址相同 M[3][4]
  7. 线性表的链式存储结构是一种( ) 存储结构 顺序存取
  8. 算法分析的目的是 分析算法的效率以求改进
  9. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 (n+1)/2
  10. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址 连续不连续都可以
  11. 不带头节点的单链表head为空的判定条件是 head==NULL
  12. head->next==NULL
  13. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行 q->next=s;s->next=p;
  14. 串是一种特殊的线性表，其特殊性体现在 数据元素是一个字符
  15. 二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围是从0到8,列下标j的范围是1到10，M的第8列和第5行共占( )字节 108
  16. 在线索二叉树中，t所指结点没左子树的充要条件是 t->ltag==1
  17. 已知某二叉树的后序遍历序列是dabec,中序遍历是debac，它的前序遍历序列是 cedba
  18. 如果T2是由有序树T转换而来的二叉树，那么T中结点的前序就是T2中结点的 前序
  19. 对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为 n
  20. 有一个有序表为（1,3,9,12,32,41,45,62,75,77,82,95,100），当二分查找值为82的结点是，( ) 次比较后查找成功 4
  21. 如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2中结点的 后序
  22. 设哈希表长m=14，哈希函数H（key）=key%11，表中已有4个结点： addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7，其余地址为空，若用二次探测再散列处理冲突，关键字为49的结点的地址是 9
  23. 在以下的叙述中，正确的是 二维数组是数据元素为线性表的线性表
  24. 线性结构的顺序存储结构是一种( )存储结构 随机存取
  25. 非空的循环单链表head的尾结点（有p所指向）满足 p->next=head
  26. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行 s->next=p->next;p->next=s;
  27. 在一个单链表中，若删除p所指结点的后续结点，则执行 p->next=p->next->next;
  28. 设有连个串p和q，求q在p中首次出现的位置的运算称作 ( )运算 模式匹配
  29. 数组A中，每个元素A的长度为3个字节，行下标i从1到8,列下标j从1到10，从首地址SA开始连续存在存储器中，该数组按行存放时，元素A[8][5]的起始地址为 SA+222
  30. 稀疏矩阵一般的压缩存储方法有两种，分别是 三元数组和十字链表
  31. 维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围是从0到8,列下标j的范围是1到10，若按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储的 ( )元素的起始地址一致 M[3][10]
  32. 采用分块查找时，若线性表共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分( ) 个结点最佳 25
  33. 在数据结构中，从逻辑上可以数据结构分成 线性结构和非线性结构
  34. 数组A中，每个元素A的长度为3个字节，行下标i从1到8,列下标j从1到10，从首地址SA开始连续存在存储器中，存放该数组至少需要的单元数是 240
  35. 如果二叉树的前序为stuwv，中序为uwtvs，则后序为 wuvts
  36. 对一个满二叉树，有m个叶子，n个结点，深度为h，则 n=2h-1
  37. 具有五层结点的二叉平衡树至少有( )个结点 15
  38. 在一个图中，所有顶点的度数之和等于所有边数的( )倍 2
  39. 二叉树的前序遍历结点顺序是abdgcefh，中序遍历的结点顺序是dgbaechf，则其后序遍历结点顺序是( ) gdbehfca
  40. 按照二叉树的定义，具有3个结点的二叉树有 种 5
  41. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的( )倍 1
  42. 有一个长度为12的有序表，按二分法查找，在表内个元素等概率情况下查找成功所需的平均比较次数为( ) 37/12
  43. 如果要求一个线性表既能较快查找，又能适应动态变化的要求，可以采用( )查找 分块

第二大题：填空题

  1. 空格串的长度等于 其包含的空格个数
  2. 已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0] [0])，这A[i][j]的地址是 LOC(A[0][0])+(n*i+j)*k
  3. 广义表(a,(a,b),d,e,((i,j),k))的长度为 5
  4. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 哈希表查找法
  5. 对n个元素的序列进行冒泡排序，最少的比较次数 n-1
  6. 在插入和选择排序中，若初始数据基本正序，则选择 插入排序
  7. 可以使用( )表示树形结构 双链表
  8. 串的两种基本存储方式是 链接存储 和()顺序存储
  9. 广义表(((a)))的表头是 ((a))
  10. 在堆排序中，快速和归并排序中，若只从平均情况下排序最快考虑，应选取( )方法 快速排序
  11. 下面程序的时间复杂度( ) s=0;for(i=0;i<n;i++) for(j=0;j<n;j++) s+=B[i][j];sum=s; O(n^2)
  12. 在双链表中，每个结点有两指针域，一个指向( )结点，一个指向后续结点 前驱
  13. 在分块查找中，首先查找 索引
  14. 在利用快速排序方法对记录（54,38,96,23,15,72,60,45,83）进行排序时，递归调用二使用的栈所能达到的最大深度为 2
  15. 在对一组记录（54,38,96,23,15,72,60,45,83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需要比较( )次 3
  16. 在HQ的链队中，判定只有一个结点的条件是 HQ->front==HQ->rear
  17. 非空的循环单链表head的尾结点（由p所指向），满足条件 head->next==p
  18. 已知二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且第一个元素的存储地址是200，这A[6][12]的地址是 332
  19. 二分查找的存储结构仅限于 顺序存储结构
  20. 已知二维数组A[10…20][5…10]采用行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，这A[18][9]的地址是 1208
  21. 在栈顶指针为HS链栈中，判定栈空的条件是 HS==NULL
  22. 单链表是( ) 链接存储表示 线性表
  23. 广义表((a),((b),c),(((d))))的表头是 ( a)
  24. 已知一个图的邻接矩阵表示，计算第i个结点的入度方法是 求矩阵第i列非0元素之和
  25. 在插入排序、希尔排序、选择排序、快速排序、堆排序中，稳定的排序有 插入排序
  26. 已知一个图的邻接矩阵表示，删除所有从i个结点出发的边的方法是 将矩阵的第i行全部置为0
  27. 在无向图G的领结矩阵A中，若A[i][j]等于1，则A[j][i]等于 1
  28. 下面程序的时间复杂度( ) for(i=0;i<n;i++) for(j=0;j<m;j++) A[i][j]=0;参考答案：O(m*n)
  29. 29、两个串相等的充分必要条件是( ) 参考答案：两个串长度相同且对应位置的字符相同
  30. 30、下面程序的时间复杂度( ) i=s=0;while(s<n){i++;s+=i;}参考答案：O(n)

第三大题：综合题 1、对关键字序列(15,22,10 13 30, 16,12,17)按从小到大进行快速排序 (1)写出排序过程中前两趟的划分结果； (2)快速排序是否是稳定的排序方法? 参考答案： (1) 第一趟12 13 10 15 30 16 22 17 第二趟10 12 13 15 17 16 22 30 （2）不稳定

2、已知序列{50 …… 参考答案：3）[61,87],170,[275],462,503,[897,908,653,512] 4) 61,[87],170,[275],462,503,[897,908,653,512] 5) 61,87,170,[275],462,503,[897,908,653,512] 6) 61,87,170,275,462,503,[897,908,653,512] 7) 61,87,170,275,462,503,[512,653],897,[908] 3、对于直接插入排序，希尔 … 参考答案：（1）希尔排序、快速排序、堆排序、归并排序（2）归并排序（3）直接选择排序、堆排序、归并排序 4、已知序列{70,83,… 参考答案：2) (70,83,100),65,10,32,7,9 3) (65,70,83,100,)10,32,7,9 4) (10,65,70,83,100,)32,7,9 5) (10,32,65,70,83,100,)7,9 6) (7,10,32,65,70,83,100,)9 5、已知序列{17,18,60,40,7,32,73,65,85}…… 参考答案：1）17，18，40，7，32，60，65，73，85 2）17，18，7，32，40，60，65，73，85 3）17，7，18，32，40，60，65，73，85 4）7，17，18，32，40，60，65，73，85 5）7，17，18，32，40，60，65，73，85

第四大题：应用题 1、阅读完成下列程序，并回答问题 #define MAXITEM 100 参考答案：（1） r[j]（2）w （3）冒泡排序算法 2、阅读完成下列程序，并回答问题 typedef struct bnode … 参考答案：（1） p!=null（2）p=stack[top]（3）二叉树中序遍历 3、阅读下列程序，回答问题 #define MAXITEM 100 … 参考答案：在线性表r中顺序查找关键字为k的结点；若找到返回位置；若找不到返回-1； 4、阅读下面代码，分析程序实现的功能 typedef struct bnode … 参考答案：（1）b!=NULL（2）return（3）查找p，q共同祖先r所指结点 5、阅读下面代码，分析程序实现的功能 typedef struct linknode … 参考答案：（1） p!=null（2）p=h2（3）实现将链表h1复制到链表h2中 6、阅读完成下列程序，并回答问题。 typedef struct bnode … 参考答案：(1) b==NULL (2)num1+num2 (3)计算二叉树双孩子结点数 7、阅读完成下列程序，并回答问题 type struct bnode{ElemType data；… 参考答案：(1) t==NULL (2) he=he2+1 (3)计算二叉树t的高度 8、阅读下列程序，回答问题 #define MAXITEM 100 struct element … 参考答案：在线性表r中二分查找关键字为k的结点；若找到返回位置；若找不到返回-1； 9、阅读下面代码，分析程序实现的功能 typedef struct tnode … 参考答案：(1) p->ltag=0(2)p->rtag=0 (3)对二叉树做中序线索化 10、设向量有A，B，C，其中A有元素n个且任何元素都不为0。阅读 … 参考答案：（1）(*p)++ （2）(*q)++ （3）将向量A分拆成向量B和C，其中大于0的元素放入B，小于0的元素放入C 11、设向量有A，B，C，其中A有个m个元素，B有n个元素。阅读完成下列程序，并回答问题。… 参考答案：（1） c[k++]=a[j++]（2） c[k++]=b[l]（3） 将向量A，B合并到C中，并保持原来顺序 第五大题：程序设计题 1、假设二叉树采用链表存储结构，设计一个算法计 … 参考答案：

void level（btree *b， btree *p，int *h， int h1）
{
if(b==NULL) *h=0; else if(p==b) *h=h1; else
{
level(p,b->left,h,h1+1);
if(*h==0) level(p,b->right,h,h1+1);
}
}

2、设计一个程序实现深度优先搜索（使用递归算法）…

void dfs(adjlist adj, int v)
{
int i;
struct edgenode *p; for(i=0;i<n;i++) visited[i]=0; visited[v]=1;
printf("%d ",v); p=adj[v].link; while(p!=NULL)
{
if(visited[p->adjvex]==0) dfs(adj,p->adjvex);
p=p->next;
}
}

3、设计一个程序实现宽度（广度）优先搜索（使用递归算法）…

void bfs(adjlist adj,int vi)
{
int front=0,rear=1,v,i; struct edgenode *p;
for(int i=0;i<MAXVEX;i++) visited[i]=0; visited[vi]=1;
printf("%d ",v); queue[rear]=vi; while(front!=rear)
 
{
front=(front+1) % MAXVEX; v=queue[front]; p=adj[v].link; while(p!=NULL)
{
if(visited[p->adjvex]==0)
{
visited[p->adjvex]=1; printf("%d ",p->adjvex); rear=(rear+1) % MAXVEX; queue[rear]=p->adjvex;
}
p=p->next;
}
}
}