数据结构算法题拟.docVIP

数据结构算法题模拟 ⑴将数组中数值为0的元素置于数组的前半部分，非0元素置于数组的后半部分。 要求保证非0元素的稳定性。 ⑵已知二叉树的中序序列和一种特殊序列，该特殊序列为奇数层为“根左右”规则遍历， 偶数层为“根右左”规则遍历。试构建出该二叉树。 ⑶查找共n个元素的循环双链表上第i（0≤i＜n）个元素的值。 ⑷编写用邻接表存储的图上，求从vi到vj节点的最短路径；并打印出所有哪些信誉好的足球投注网站的路径。 『注』 ①本模拟题与高校自主命题的数据结构卷算法题目部分命题思路相似。有需要的人可试做练习； ②详细算法在下一页。 ☆ ★ ☆ ★ ☆ 代 ★ 码 ☆ 详 ★ 解 ☆ ★ ☆ ★ ☆ 〖注〗黑绿色加粗部分为主题，灰色部分可以不写。 ⑴『思路点评』 很多人看到这道题目首先想到的是快速排序的定位算法部分（多为partition、pivot、split等函数命名）。但这道题目要求非“0”元素的部分具有稳定性。因此，要从稳定性(和归位性)的算法角度出发，如‘插入排序’、‘冒泡排序’，这些排序的时间复杂度在特殊的情况下为ο(n)。详细算法如下∶ #include stdio.h #include stdlib.h void zeroBefore(int *a, int n) /* 函数功能：元素0置前 */ { int i = n, p = -1; /* 模仿插入排序及冒泡排序。p为非0元素的一端。 */ while (--i = 0) { if (a[i] == 0) { if (p == -1) { p = i; /* 确定非0元素的插入位置。 */ } } else { if (p != -1) { a[p--] = a[i]; /* 非0元素插入底端 */ a[i] = 0; /* 元素0进行冒泡向上（左）移动。 */ } } } } #define N 10 int main(void) { int a[N] = {0, 3, 0, 0, 2, 0, 4, 5, 0, 8}; int i; zeroBefore(a, N); printf(数据排序之后：); for (i = 0; i N; i++) printf(%d , a[i]); printf(\n); system(pause); return EXIT_SUCCESS; } ⑵『思路点评』 这道题不同于其他二叉树的构建题目。如‘先序—中序’遍历、‘后序—中序’遍历，可以用递归方法。然而，该题目只能用非递归算法。主要思路是根据二叉排序树的插入过程，与二叉排序树不同的是比较两个元素分别于中序遍历字符串的下标位置。根据下标位置的大小确定待插入元素于当前元素的左右子树。复杂度为ο(n*log2(n))。详细算法如下∶ #include conio.h #include stdio.h #include stdlib.h #include string.h #include malloc.h typedef struct BiNode /* 二叉链表定义 */ { char data; /* 数据域 */ struct BiNode *left, *right; /* 左、右子树 */ } BiNode; typedef struct BiTree /* 二叉树 */ { BiNode *root; /* 根节点 */ } BiTree; BiNode* new_BiNode(char data) /* 动态申请新节点 */ { BiNode *p = (BiNode*) malloc(sizeof(BiNode)); p-data = data; p-left = NULL; p-right = NULL; return p; } int indexOf(char *str, char data) /* 查找元素在字符串的位置 */ { int i = 0; while (str[i] != \0) { if (str[i] == data) { return i; } i++; } return -1; } void mkBiTree(BiTree *t, char *spOrd, char *inOrd) /* 函数：根据中序序列和特殊序列构建二叉树 */ { unsigned int len = strlen(spOrd); BiNode *p; int i, j, k; if (len == 0 || len !=